#define REP(i,j,k) for(int i=j;i<=k;i++)

 #include<iostream>

 using namespace std;

 const int mod=;

 struct matrix

 {

     int d[][];

 };

 matrix I,mat,zero;

 int T,n;

 void Init()

 {

     memset(I.d,,sizeof(I.d));memset(mat.d,,sizeof(mat.d));memset(zero.d,,sizeof(zero.d));

     I.d[][]=I.d[][]=I.d[][]=;

     mat.d[][]=mat.d[][]=mat.d[][]=mat.d[][]=;

 }

 matrix Mult(matrix x,matrix y)

 {

     matrix ans=zero;

     REP(i,,) REP(j,,) REP(k,,)

         ans.d[i][j]=(ans.d[i][j]+x.d[i][k]*y.d[k][j])%mod;

     return ans;

 }

 int modexp(int x)

 {

     matrix ret=I,tmp=mat;

     while(x)

     {

         if(x&) ret=Mult(ret,tmp);

         tmp=Mult(tmp,tmp);

         x>>=;

     }

     return (ret.d[][]+ret.d[][]+ret.d[][])%mod;

 }

 int solve(int x)

 {

     if(x<=) return ;

     return modexp(x-);

 }

 int main()

 {

     Init();

     cin>>T;

     REP(i,,T)

     {

         cin>>n;

         cout<<solve(n)<<endl;

     }

     return ;

 }