#include<bits/stdc++.h>

 using namespace std;

 int MOD = ;

 struct Mat

 {

     int a[][];

     int n, m;//n为行数，m为列数

     Mat(int n, int m):n(n), m(m)

     {

         memset(a, , sizeof(a));

     }

     void init()

     {

         for(int i = ; i < n; i++)a[i][i] = ;//初始化成单位矩阵

     }

     void output()

     {

         for(int i = ; i < n; i++)

         {

             for(int j = ; j < m; j++)

             {

                 cout<<a[i][j]<<" ";

             }

             cout<<endl;

         }

     }

 };

 Mat mul(Mat a, Mat b)//矩阵乘法

 {

     Mat tmp(a.n, b.m);//矩阵乘法结果矩阵行数为a的行数，列数为b的列数

     for(int i = ; i < a.n; i++)

     {

         for(int j = ; j < b.m; j++)

         {

             for(int k = ; k < a.m; k++)//a.m == b.n(乘法的前提条件)

             {

                 tmp.a[i][j] += (a.a[i][k] * b.a[k][j] % MOD);

                 tmp.a[i][j] %= MOD;

             }

         }

     }

     return tmp;

 }

 Mat pow(Mat a, int n)

 {

     Mat tmp(a.n, a.m);

     tmp.init();

     while(n)

     {

         if(n & )tmp = mul(tmp, a);

         n /= ;

         a = mul(a, a);

     }

     return tmp;

 }

 int main()

 {

     int T, n;

     cin >> T;

     Mat a(, );

     a.a[][] = , a.a[][] = ;

     a.a[][] = , a.a[][] = ;

     while(T--)

     {

         cin >> n;

         Mat ans = pow(a, n);

         //ans.output();

         int x = ans.a[][], y = ans.a[][];

         cout<<( * x - ) % MOD<<endl;

     }

 }