#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<vector>

#include<queue>

#include<stack>

#include<set>

#include<map>

#include<algorithm>

using namespace std;

typedef long long int LL;

const LL mt_MAXN=60;const LL mt_MAXM=60;

struct Matrix

       {

        LL n,m;

		LL MOD;

		LL a[mt_MAXN][mt_MAXM];

		void clear()

				{

				 n=m=0;

				 memset(a,0,sizeof(a));

				}

		Matrix operator +(const Matrix &b)const

            {

			Matrix tmp;

			tmp.n=n;tmp.m=m;tmp.MOD=MOD;

            for(LL i=0;i<n;++i)

				for(LL j=0;j<m;++j)

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

 			 return tmp;

         	}

        Matrix operator -(const Matrix &b)const

            {

			Matrix tmp;

			tmp.n=n;tmp.m=m;tmp.MOD=MOD;

            for(LL i=0;i<n;++i)

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

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

 			 return tmp;

         	}

		Matrix operator *(const Matrix &b)const

			{

			 Matrix tmp;

			 tmp.clear();

			 tmp.n=n;tmp.m=b.m;tmp.MOD=MOD;

 			 for(LL i=0;i<n;++i)

				for(LL j=0;j<b.m;++j)

					for(LL k=0;k<m;++k)

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

			 return tmp;

			}

		Matrix iden()

				{

				 Matrix x;

				 memset(x.a,0,sizeof(x.a));

				 x.m=n;x.n=n;

				 x.MOD=MOD;

				 for(LL i=0;i<n;++i)

				     x.a[i][i]=1;

				 return x;

				}

		Matrix pow(LL t)

				{

				 Matrix now;

				 now.n=n;now.m=m;now.MOD=MOD;

				 memset(now.a,0,sizeof(now.a));

				 for(LL i=0;i<n;++i)

					for(LL j=0;j<m;++j)

						now.a[i][j]=a[i][j];

				 for(LL i=1;i<t;i++)

					now=now*now;

				 return now;

				}

		Matrix qpow(LL t)

				{

				 if(n==0)return iden();

				 Matrix now;

				 now.clear();

				 now.n=n;now.m=m;now.MOD=MOD;

				 now=pow(1);

				 Matrix ans;

				 	 ans.clear();

				 ans.n=n;ans.m=m;ans.MOD=MOD;

			     ans=ans.iden();

				 while(true)

					{

					 if(t%2==1)ans=ans*now;

					 t=t/2;

					 now=now*now;

					 if(t==0)break;

					}

				 return ans;

				}

	   };

int main()

{

 int T;

 scanf("%d",&T);

 Matrix p;

 p.clear();

 p.n=p.m=3;

 p.a[0][0]=2;p.a[0][1]=1;

 p.a[1][0]=p.a[1][1]=p.a[1][2]=2;

 p.a[2][1]=1;p.a[2][2]=2;

 p.MOD=10007;

 Matrix p0;

 p0.clear();

 p0.n=3;p0.m=1;

 p0.a[0][0]=2;

 p0.a[1][0]=2;

 while(T--)

 	{

 	 LL n;

	 scanf("%lld",&n);

	 Matrix pn=p.qpow(n-1);

	 Matrix ans=pn*p0;

	 printf("%lld\n",ans.a[0][0]);

	}

 return 0;

}