#include <bits/stdc++.h>
using namespace std;

// BEGIN template
#define FASTIO  std::ios::sync_with_stdio(false)
#define SHOW(X) (cout << ">>>>> " << #X << ": " << (X) << endl), fflush(stdout)
#define  rp(ITER,BEG,END) for (int ITER = BEG, ENDD = END; ITER <= ENDD; ITER++)
#define rpd(ITER,BEG,END) for (int ITER = BEG, ENDD = END; ITER >= ENDD; ITER--)
#define LSOne(X)  ((X)&(-(X)))

#define MAXN      5005
#define MAXLOGN   18
#define MOD       10007
#define oo        0x3f3f3f3f
#define OO        0x3f3f3f3f3f3f3f3fL
#define MAX_PRIME 1000000
#define TOT_PRIME 100000

#define ff first
#define ss second
#define pb push_back
#define eb emplace_back

enum {WHITE=0,GRAY,BLACK};
enum {UNVISITED=-1};

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,int> lli;
typedef vector<int> vi;

int pass = 1;
// END template

const int all = 0x1ff;
inline int gmask(int u) {
  return 1<<(u-1);
}
inline int has(int mask, int u) {
  return (mask&gmask(u))>>(u-1);
}
inline int rem(int mask, int u) {
  return mask&(~gmask(u));
}
int nei[][4] = {
  {0,0,0,0},
  {2,4,0,0},
  {1,3,5,0},
  {2,6,0,0},
  {1,5,7,0},
  {2,4,6,8},
  {3,5,9,0},
  {4,8,0,0},
  {5,7,9,0},
  {6,8,0,0}
};

short dp[MAXN][3][3][3][3][3][3][3][3][3];
short f(int i, int m1, int m2) {
  short& ans = dp[i][has(m2,1)?2:has(m1,1)][has(m2,2)?2:has(m1,2)][has(m2,3)?2:has(m1,3)][has(m2,4)?2:has(m1,4)][has(m2,5)?2:has(m1,5)][has(m2,6)?2:has(m1,6)][has(m2,7)?2:has(m1,7)][has(m2,8)?2:has(m1,8)][has(m2,9)?2:has(m1,9)];
  if (ans >= 0) return ans;
  if (!m1) {
    if (i == 1) return ans = (m2 ? 0 : 1);
    return ans = f(i-1,all&~m2,0);
  }
  ans = 0;
  for (int j = 1; j <= 9; j++) if (has(m1,j)) {
    m1 = rem(m1,j);
    ans = (ans+f(i,m1,m2|gmask(j)))%MOD;
    for (int k = 0; k < 4 && nei[j][k]; k++) if (has(m1,nei[j][k])) {
      ans = (ans+f(i,rem(m1,nei[j][k]),m2))%MOD;
    }
    return ans;
  }
}

int main() {
  memset(dp,-1,sizeof dp);
  int T;
  cin >> T;
  while (T--) {
    int N;
    cin >> N;
    cout << (N==0 ? 1 : (N&1 ? 0 : f(N,all,0))) << endl;
  }
  return 0;
}