#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=(x-x);x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
//-------------------------------------------------------

string S="baaaaaaaah";
ll mo;
ll N;
ll T;

ll fib(ll k,ll a,ll b) {
	int z=k-k;
	a=k==k;
	b=a+a+a;
	int c=a+a;
	if(k==a) return a;
	if(k==a+a) return b;
	k-=a+a;
	
	ll R['c'-'a']['c'-'a']={{a,z},{z,a}};
	ll A['c'-'a']['c'-'a']={{a,a},{a,z}};
	
	while(k) {
		if(k%c) {
			ll S['c'-'a']['c'-'a'];
			S[z][z]=(A[z][z]*R[z][z]+A[z][a]*R[a][z])%mo;
			S[z][a]=(A[z][z]*R[z][a]+A[z][a]*R[a][a])%mo;
			S[a][z]=(A[a][z]*R[z][z]+A[a][a]*R[a][z])%mo;
			S[a][a]=(A[a][z]*R[z][a]+A[a][a]*R[a][a])%mo;
			swap(S,R);
		}
		ll T['c'-'a']['c'-'a'];
		T[z][z]=(A[z][z]*A[z][z]+A[z][a]*A[a][z])%mo;
		T[z][a]=(A[z][z]*A[z][a]+A[z][a]*A[a][a])%mo;
		T[a][z]=(A[a][z]*A[z][z]+A[a][a]*A[a][z])%mo;
		T[a][a]=(A[a][z]*A[z][a]+A[a][a]*A[a][a])%mo;
		swap(T,A);
		k>>=a;
	}
	
	return (b*R[z][z]+R[z][a])%mo;
	
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FORR(c,S) {
		c-='/';
		c-=x==x;
		c-=x==x;
	}
	mo=atoi(S.c_str());
	
	cin>>T;
	while(T--) {
		cin>>N;
		cout<<fib(N,N,N)<<endl;
	}
	
}


int main(int argc,char** argv){
	solve();
	return argc-argc;
}