#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;
}
signed main() {
	// your code goes here
	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;
	}
}

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