C++ :

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<map>
#include<bitset>
#include<stack>
#include<vector>
#include<set>
using namespace std;
#define MAXN 10010
#define MAXM 10010
#define INF 1000000000
#define MOD 1000000007
#define ll long long
#define eps 1e-8
#define MAXL 1010
char bnin[MAXL];
struct bn{
	char x[MAXL];int n;
	bn(){memset(x,0,sizeof(x));n=0;}
	bn(int X){memset(x,0,sizeof(x));n=0;while(X){x[++n]=X%10;X/=10;}}
	friend istream &operator >>(istream &input,bn &x){int i;input>>bnin;memset(x.x,0,sizeof(x.x));x.n=strlen(bnin);for(i=1;i<=x.n;i++){x.x[i]=bnin[x.n-i]-'0';}return input;}
	friend ostream &operator <<(ostream &output,bn x){int i;if(!x.n){output<<0;}for(i=x.n;i;i--){output<<int(x.x[i]);}return output;}
	void rd(){int i;scanf("%s",bnin);n=strlen(bnin);for(i=1;i<=n;i++){x[i]=bnin[n-i]-'0';}}
	void pt(){int i;if(!n){printf("0");}for(i=n;i;i--){printf("%d",x[i]);}}
	void half(){int i;for(i=n;i;i--){x[i-1]+=(x[i]%2)*10;x[i]/=2;}x[0]=0;while(!x[n]&&n){n--;}}
	bn operator =(ll y){for(this->n=1;y!=0;this->x[this->n]=y%10,y/=10,this->n++){}this->n--;return *this;}
	friend bool operator <(bn x,bn y){int i;if(x.n!=y.n){return x.n<y.n;}for(i=x.n;i;i--){if(x.x[i]!=y.x[i]){return x.x[i]<y.x[i];}}return 0;}
	friend bool operator ==(bn x,bn y){int i;if(x.n!=y.n){return 0;}for(i=x.n;i;i--){if(x.x[i]!=y.x[i]){return 0;}}return 1;}
	friend bool operator >(bn x,bn y){return !(x<y|x==y);}
	friend bool operator <=(bn x,bn y){return x<y|x==y;}
	friend bool operator >=(bn x,bn y){return x>y|x==y;}
	friend bool operator <(bn x,ll y){return x<bn(y);}
	friend bool operator ==(bn x,ll y){return x==bn(y);}
	friend bool operator >(bn x,ll y){return x==bn(y);}
	friend bool operator <=(bn x,ll y){return x==bn(y);}
	friend bool operator >=(bn x,ll y){return x==bn(y);}
	friend bool operator <(ll x,bn y){return bn(x)<y;}
	friend bool operator ==(ll x,bn y){return bn(x)==y;}
	friend bool operator >(ll x,bn y){return bn(x)==y;}
	friend bool operator <=(ll x,bn y){return bn(x)==y;}
	friend bool operator >=(ll x,bn y){return bn(x)==y;}
	friend bn operator +(bn x,bn y){bn z;int i;for(i=1;i<=x.n|i<=y.n;i++){z.x[i]+=x.x[i]+y.x[i];z.x[i+1]+=z.x[i]/10;z.x[i]%=10;}z.n=max(x.n,y.n);if(z.x[z.n+1]){z.n++;}return z;}
	friend bn operator -(bn x,bn y){bn z;int i;for(i=1;i<=x.n|i<=y.n;i++){z.x[i]+=x.x[i]-y.x[i];if(z.x[i]<0){z.x[i+1]--;z.x[i]+=10;}}z.n=max(x.n,y.n);while(!z.x[z.n]&&z.n){z.n--;}return z;}
	friend bn operator *(bn x,bn y){bn z;int i,j;for(i=1;i<=x.n;i++){for(j=1;j<=y.n;j++){z.x[i+j-1]+=x.x[i]*y.x[j];z.x[i+j]+=z.x[i+j-1]/10;z.x[i+j-1]%=10;}}z.n=x.n+y.n;while(!z.x[z.n]&&z.n){z.n--;}return z;}
	friend bn operator +(bn x,ll y){return x+bn(y);}
	friend bn operator -(bn x,ll y){return x-bn(y);}
	friend bn operator *(bn x,ll y){return x*bn(y);}
	friend bn operator +(ll x,bn y){return bn(x)+y;}
	friend bn operator -(ll x,bn y){return bn(x)-y;}
	friend bn operator *(ll x,bn y){return bn(x)*y;}
	friend bn operator /(bn x,bn y){bn z;bn l,r,mid;l=0;r=x;while(l<=r){mid=l+r;mid.half();if(mid*y<=x){z=mid;l=mid+1;}else{r=mid-1;}}return z;}
	friend bn operator /(bn x,ll y){return x/bn(y);}
	friend bn operator /(ll x,bn y){return bn(x)/y;}
	friend bn operator %(bn x,bn y){return x-(y*(x/y));}
	bn operator +=(bn x){(*this)=(*this)+x;return (*this);}
	bn operator -=(bn x){(*this)=(*this)-x;return (*this);}
	bn operator *=(bn x){(*this)=(*this)*x;return (*this);}
	bn operator /=(bn x){(*this)=(*this)/x;return (*this);}
	bn operator %=(bn x){(*this)=(*this)%x;return (*this);}
	bn operator +=(ll x){(*this)=(*this)+x;return (*this);}
	bn operator -=(ll x){(*this)=(*this)-x;return (*this);}
	bn operator *=(ll x){(*this)=(*this)*x;return (*this);}
	bn operator /=(ll x){(*this)=(*this)/x;return (*this);}
	bn operator %=(ll x){(*this)=(*this)%x;return (*this);}
	ll tonum(){ll re=0;int i;for(i=n;i;i--){re*=10;re+=x[i];}return re;}
	friend bn sqrt(bn x){bn z;bn l,r,mid;l=0;r=x;while(l<=r){mid=l+r;mid.half();if(mid*mid<=x){z=mid;l=mid+1;}else{r=mid-1;}}return z;}
};
bool jud(bn &x){
	if(!x.n){
		return 0;
	}
	return x.x[1]&1;
}
bn cal(bn x,bn X,bn Y){
	if(x==0){
		return Y;
	}
	if(jud(x)){
		x.half();
		return cal(x,X,X+Y);
	}else{
		x.half();
		return cal(x,X+Y,Y);
	}
}
bn a;
int main(){
	int tmp;
	scanf("%d",&tmp);
	while(tmp--){
		cin>>a;
		while(!jud(a)){
			a.half();
		}
		a.half();
		cout<<cal(a,bn(1),bn(1))<<endl;
	}
	return 0;
}

/*

*/

Python :

# coding=utf-8

def dfs(a):
    if a <= 1:
        return a
    if a % 2 == 1:
        if a//2 not in dct:
            dct[a//2] = dfs(a//2)
        if a // 2 + 1 not in dct:
            dct[a // 2 + 1] = dfs(a // 2 + 1)
        return dct[a//2] + dct[a//2+1]
    else:
        if a // 2 not in dct:
            dct[a // 2] = dfs(a // 2)
        return dct[a//2]


line = input().strip()
T = int(line)
dct = {}

for i in range(T):
    line = input().strip()
    a = int(line)
    print(dfs(a))