#include<stdio.h>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#define ll long long
#define mod 10007
using namespace std;
struct zxy{
    ll a[2][2];
}jichu,a,b;
ll n;
inline ll in(){
    ll x=0,f=1;
    char ch=getchar();
    while(ch<‘0‘||ch>‘9‘) {if(ch==‘-‘) f=-1; ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();
    return x*f;
}
inline zxy mult(zxy a,zxy b){
    zxy c;
    memset(c.a,0,sizeof(c.a));
    for (int i=0; i<=1; ++i)
        for (int j=0; j<=1; ++j)
            for (int k=0; k<=1; ++k)
                c.a[i][j]+=(a.a[i][k]*b.a[k][j]+2*mod)%mod,c.a[i][j]=(c.a[i][j]+2*mod)%mod;
    return c;
}
inline zxy ksm(zxy a,ll k){
    if (k==0) return jichu;
    if (k==1) return a;
    zxy tt=ksm(a,k>>1);
    if (k&1) return mult(a,mult(tt,tt));
    return mult(tt,tt);
}
int main(){
    int T=in();
    memset(jichu.a,0,sizeof(jichu.a));
    memset(b.a,0,sizeof(b.a));
    memset(a.a,0,sizeof(a.a));
    jichu.a[0][0]=jichu.a[1][1]=1;
    b.a[0][0]=2;b.a[1][0]=8;
    a.a[0][1]=1;a.a[1][0]=-2+mod,a.a[1][1]=4;
    while(T--){
        n=in();
        if (n&1) printf("0\n");
        else{
            n=n/2-2;
            if (n<2) printf("%lld\n",b.a[n][0]);
            else{ zxy ans=mult(ksm(a,n-1),b);printf("%lld\n",ans.a[1][0]);}
        }
    }
    return 0;
}