#include<stdio.h>
int main()
{
    long long int k,t,i,n,a[100];
    scanf("%lld",&t);
    a[0]=0;
    a[1]=1;
    for(i=2;i<100;i+=2){	//定义斐波拉切数列
        a[i]=a[i-1]+a[i-2];
        a[i+1]=a[i]+a[i-1];
    }
    while(t--){
        k=1;				//每次重新定义k
        scanf("%lld",&n);
        if(n>0){
            for(i=0;;i++){	//判断是2的多少次方
                k*=2;
                if(k>n){
                    printf("%lld\n",a[i+1]);
                    break;
                }
            }
        }else printf("%lld",a[0]);
    }
    return 0;
}