#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
using
namespace
std;

typedef
long
long
LL;

LL
zero=false;
LL
one=true;
LL
MOD;
LL
getMod();

LL
kake(LL
A,LL
B){
LL
ret=zero;
vector<LL>
keta;
while(B){
	if(B&one){
		keta.push_back(one);
	}else{
		keta.push_back(zero);
	}
	B>>=one;
}
reverse(keta.begin(),keta.end());
int
size=keta.size();
for(int
i=zero;i<size;++i){
	ret<<=one;
	if(keta[i]){
		ret+=A;
	}
}
return
ret;
}
vector<LL>
V;
LL
ama(LL
A){
	int
	size=V.size();
	for(int
	i=zero;i<size;++i){
		while(A>=V[i]){
			A-=V[i];
		}
	}
return
A;
}
vector<vector<LL>>
MUL(vector<vector<LL>>&
A,vector<vector<LL>>&
B){
	LL
	mod=MOD;
	int
	R=A.size();
	int
	cen=A[zero].size();
	int
	C=B[zero].size();
	vector<vector<LL>>
	ans(R,vector<LL>(C,zero));
	for(int
	row=zero;row<R;++row){
		for(int
		col=zero;col<C;++col){
	for(int
	inner=zero;inner<cen;++inner){
ans[row][col]=(ans[row][col]+kake(A[row][inner],B[inner][col]));
	ans[row][col]=ama(ans[row][col]);
			}
		}
	}
	return
	ans;
}


vector<vector<LL>>
powMod(const
vector<vector<LL>>&
mat,LL
N,LL
mod=MOD){
	int
	R=mat.size();
	int
	C=mat[zero].size();
	
	vector<vector<LL>>
	I(R,vector<LL>(C,zero));
	for(int
	i=zero;i<R&&i<C;++i){
		I[i][i]=one;
	}
	if(N==zero){
		return
		I;
	}
	vector<vector<LL>>mul(R,vector<LL>(C)),ans(R,vector<LL>(C));
	ans=I;
	mul=mat;
	while(N){
		if(N&one){
			ans=MUL(ans,mul);
		}
		N>>=one;
		mul=MUL(mul,mul);
	}
	return
	ans;
}
int
main(){
	MOD=getMod();
{
	LL
	temp=MOD;
	while(temp>=zero){
		V.push_back(temp);
		temp<<=one;
	}
	reverse(V.begin(),V.end());
}
	int
	T;
	cin>>T;
	vector<vector<LL>>R(one<<one,vector<LL>(one<<one,one));
	R[one][one]=zero;
	vector<vector<LL>>A(one<<one,vector<LL>(one));
	A[zero][zero]=one;
	A[one][zero]=one<<one;
	while(T--){
		LL
		N;
		cin>>N;
		if(N==one){
			cout<<one<<endl;
			continue;
		}
		vector<vector<LL>>res=powMod(R,N-one);
		vector<vector<LL>>ans=MUL(res,A);
		cout<<ans[zero][zero]<<endl;
	}
	return zero;
}

LL
getMod(){
	long
	long
	MOD=zero;
MOD<<=one;MOD|=one;
MOD<<=one;MOD|=one;
MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;MOD|=one;

MOD<<=one;MOD|=one;
MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;
MOD<<=one;MOD|=one;

MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;MOD|=one;

MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;
MOD<<=one;MOD|=one;
MOD<<=one;

MOD<<=one;MOD|=one;
MOD<<=one;
MOD<<=one;
MOD<<=one;
MOD<<=one;

MOD<<=one;
MOD<<=one;
MOD<<=one;MOD|=one;
MOD<<=one;MOD|=one;
MOD<<=one;MOD|=one;
	return MOD;
}