#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 add(LL a,LL b){
	while(b!=zero){
		LL c = (a&b)<<one;
		a^=b;
		b=c;
	}
	return a;
}
LL sub(LL a,LL b){
	return add(a,add(~b,one));
}
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=add(i,one)){
	ret <<= one;
	if( keta[i] ){
		ret = add(ret,A);
	}
}
return ret;
}
vector<LL> V;
LL ama(LL A){
	int size = V.size();
	for(int i=zero;i<size;i=add(i,one)){
		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=add(row,one)){
		for(int col=zero;col<C;col=add(col,one)){
			for(int inner=zero;inner< cen;inner=add(inner,one)){
ans[row][col] = add(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=add(i,one)){
		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;
}
signed 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;
	int count = zero;
	while(count<T){
		count = add(count,one);
		
		LL N;
		cin>>N;
		if( N== one){
			cout << one << endl;
			continue;
		}
		
		vector<vector<LL> > res = powMod(R,N);
		vector<vector<LL> > ans = MUL(res,A);
		cout << ans[one][zero] << endl;
	}
}

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;
}