佳佳最近在研究Finbonacci数列:

F(0)=1;
F(1)=1;
F(n)=F(n-1)+F(n-2); (n>=2)

他把Finbonacci数列的各项数字排到一起，构造了一个奇怪的自然数：

1123581321345589…………

这个无聊自然数也许有一些有用的性质，不过佳佳要先能搞清楚这个大数的第k位是多少。

输入的第一行是一个整数t，表示共有t组询问，接下来t行每行是一个整数k(k<=100000)，表示佳佳在问你这个怪数的第k位是几

对每个询问，输出被询问的数字。

5
1
2
3
4
5

1
1
2
3
5

 

#include<iostream>
using namespace std;
int main(){
    int k,t,a,b,q,i=3,c,d,temp,ta,tb,tc,td,f[110000],p[1000];
    f[1]=f[2]=1;
    a=b=ta=tb=1;c=d=tc=td=2;
    while(i<100001){
        k=1,temp=0;
        while(b>=a){
            p[k++]=(f[b]+f[d]+temp)%10;
            temp=(f[b]+f[d]+temp)/10;
            b--;d--;
        }
        if(d==c-1)
            p[k]=temp;
        else
            p[k]=f[c]+temp;
        if(p[k]==0)
            k--;
        for(int j=k;j>0;--j){
            f[i++]=p[j];
        }
        b=td,a=tc;
        c=td+1,d=td+k;
        ta=a,tb=b,tc=c,td=d;
    }
    cin>>t;
    while(t--){
        cin>>q;
        cout<<f[q]<<endl;
    }
}