#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long LL;
const int INF=0x4fffffff;
const double EXP=1e-5;
const int MS=10;
const int SIZE=1000;

const int mod=10007;

typedef vector<vector<int> > mat;


  //  calc   A*B

mat mul(mat &A,mat &B)
{
  mat C(A.size(),vector<int>(B[0].size()));

  for(int i=0;i<A.size();i++)
  {
        for(int k=0;k<B.size();k++)
        {
              for(int j=0;j<B[0].size();j++)
              {
                    C[i][j]=(C[i][j]+(LL)A[i][k]*B[k][j])%mod;    //  note   overflow
              }
        }
  }
  return C;
}

  //   calc  A^n


  mat pow(mat A,LL n)
  {
        mat B(A.size(),vector<int>(A[0].size()));
        for(int i=0;i<A.size();i++)
            B[i][i]=1;
        while(n>0)
        {
              if(n&1)
                  B=mul(B,A);
              A=mul(A,A);
              n>>=1;
        }
        return B;
  }

  LL n;
void solve()
{
      mat A(3,vector<int>(3));
      A[0][0]=2;A[0][1]=1;A[0][2]=0;
      A[1][0]=2;A[1][1]=2;A[1][2]=2;
      A[2][0]=0;A[2][1]=1;A[2][2]=2;
      A=pow(A,n);
      printf("%d\n",A[0][0]);
}

int main()
{
      int T;
      scanf("%d",&T);
      while(T--)
      {
            scanf("%lld",&n);
            solve();
      }
      return 0;
}