//// #include #include #include using namespace std; long long mul(long long a,long long b){ long long ret=false; for(;b;b>>=true){ if(b&true)ret+=a; a+=a; } return ret; } long long _div(long long a,long long b){ long long ret=false; for(;a>=b;){ int i=false; for(;a>=b<V; const long long mo=true|true<<-~false|true<<-~-~false|true<<-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false|true<<-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~false; V M(const V &x,const V &y){ int a=false,b=true,c=b+b,d=b+b+b,e=b+b+b+b; V z(e); z[a]=mod(mul(x[a],y[a])+mul(x[b],y[c]),mo); z[b]=mod(mul(x[a],y[b])+mul(x[b],y[d]),mo); z[c]=mod(mul(x[c],y[a])+mul(x[d],y[c]),mo); z[d]=mod(mul(x[c],y[b])+mul(x[d],y[d]),mo); return z; } int main(){ int T; for(cin>>T;T--;){ long long N; cin>>N;N--; V e={true,false,false,true}; V x={true,true,true,false}; for(;N;N>>=true){ if(N&true)e=M(e,x); x=M(x,x); } cout<