#include <stdio.h>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
#include <fstream>
#include <cassert>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include <sys/resource.h>

using namespace std;
using namespace __gnu_pbds;

#ifdef loc

template<class T, class U> ostream &operator<<
  (ostream &out,
   const pair<T, U> &a) {
  out << "[" << a.first << " " << a.second << "]";
  return out;
}

template<class T>
  ostream &operator<<(ostream &out,
                      const vector<T> &a) {
  out << "[ ";
  for(auto &it : a) {
    out << it << " ";
  }
  out << "]";
  return out;
}

template<class T> ostream &operator<<(ostream &out, const set<T> &a) {
    out << "[ ";
    for(auto &it : a) {
      out << it << " ";
    }
    out << "]";
    return out;
  }

template<class T>
  ostream &operator<<(ostream &out,
                      const multiset<T> &a) {
  out << "[ ";
  for(auto &it : a) {
    out << it << " ";
  }
  out << "]";
  return out;
}

template<class T, class U>
  ostream &operator<<(ostream &out,
                      const map<T, U> &a) {
  for(auto &it : a) {
    out << it.first << " -> " << it.second << " | ";
  }
  return out;
}

template<class T, class U>
  ostream &operator<<(ostream &out,
                      const multimap<T, U> &a) {
  for(auto &it : a) {
    out << it.first << " -> " << it.second << " | ";
  }
  return out;
}

#define pra(a, n) cerr << #a << " : "; for(int i = 0; i <= n; ++i) cerr << a[i] << " "; cerr << endl;

#define praa(a, n, m) cerr << #a << " : " << endl; for(int i = 0; i <= n; ++i) { for(int j = 0;j <= m; ++j) cerr << a[i][j] << " "; cerr << endl; }

#define pr(...) __f(#__VA_ARGS__, __VA_ARGS__)

#define prl() cerr << __LINE__ << ": " << __PRETTY_FUNCTION__ << endl;

template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cerr << name << " : " << arg1 << std::endl;
}

template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1,
         Args &&... args) {
  const char *comma = strchr(names + 1, ',');
  cerr.write(names,
             comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}

#define gc getchar

#else

#define pr(...)
#define pra(a, n)
#define praa(a, n, m)
#define prl()
#define gc getchar

#endif

#define mod 10007

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
ordered_set;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;
typedef vector<vector<pair<int, int>>> vvpii;
typedef vector<ll> vl;
typedef vector<vector<ll>>vvl;
typedef pair<ll, ll> pll;
typedef vector<pair<ll, ll>> vpll;
typedef vector<vector<pair<ll, ll>>> vvpll;

template<typename T, typename U> static void amin(
  T &x, U y) {
  if(y < x) {
    x = y;
  }
}

template<typename T, typename U> static void amax(
  T &x, U y) {
  if(x < y) {
    x = y;
  }
}

ll po(ll a, ll b, ll m = mod) {
  ll res = 1;
  a %= m;
  //assert(b >= 0);
  for(; b; b >>= 1) {
    if(b & 1) {
      res = (res * a) % m;
    }
    a = (a * a) % m;
  }
  return res;
}

#define inc_stack_limit const rlim_t kStackSize = 64 * 1024 * 1024; struct rlimit rl; rl.rlim_cur = kStackSize; setrlimit(RLIMIT_STACK, &rl);
#define sz(a) int((a).size())
#define all(a) (a).begin(),(a).end()
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define rep(i, s, n)  for(int i = s; i <= (n); ++i)
#define rev(i, n, s)  for(int i = (n); i >= s; --i)
#define fore(x, a) for(auto &&x : a)
#define fill(a, x) memset((a), (x), sizeof(a))
const double eps = 1e-6;
#define tcase int __T; cin >> __T; rep(Tc, 1, __T)
#define ass(n, l, r) assert(n >= l and n <= r)
#define endl '\n'

inline int add(int a, int b, int m = mod) {
  a += b;
  if(a >= m) {
    a -= m;
  }
  return a;
}

inline int mul(int a, int b, int m = mod) {
  return (int)(((ll)a * (ll)b) % m);
}

inline int ri() {
  int c = gc();
  int ret = 0;
  while(c < '0' || c > '9') {
    c = gc();
  }
  while(c >= '0' && c <= '9') {
    ret = 10 * ret + c - 48;
    c = gc();
  }
  return ret;
}


#define N 100005

int dp[5005][1 << 9];
int mm[1 << 9];
int dp2[10][511];
int a[9][9];
int f[9];


int main() {
  rep(i, 0, 511) {
    fill(a, 0);
    int c1 = 0, c2 = 0;
    vi d, e;
    d.push_back(-1);
    rep(i1, 0, 2) {
      rep(j1, 0, 2) {
        if((i >> (i1 * 3 + j1)) & 1) {
          if(!((i1 + j1) & 1)) {
            c1++;
            d.push_back(i1 * 3 + j1);
          } else {
            c2++;
            e.push_back(i1 * 3 + j1);
          }
        }
      }
    }
    //pr(i);
    //pr(d, e);
    if(c1 == c2) {
      rep(i1, 0, 2) {
        rep(j1, 0, 2) {
          rep(i2, 0, 2) {
            rep(j2, 0, 2) {
              if(((i >> (i1 * 3 + j1)) & 1) && ((i >> (i2 * 3 + j2)) & 1) &&
                 (abs(i1 - i2) + abs(j1 - j2) == 1) && (!((i1 + j1) & 1))) {
                a[i1 * 3 + j1][i2 * 3 + j2] = 1;
              }
            }
          }
        }
      }
      int c = c1;
      rep(i1, 0, c - 1) {
        f[e[i1]] = i1;
      }
      fill(dp2, 0);
      dp2[0][0] = 1;
      rep(i1, 1, c) {
        dp2[i1][0] = 1;
        rep(j, 1, (1 << c) - 1) {
          dp2[i1][j] = dp2[i1 - 1][j];
          rep(k, 0, c - 1) {
            if(a[d[i1]][e[k]] && ((j >> k) & 1)) {
              dp2[i1][j] += dp2[i1 - 1][j ^ (1 << k)];
            }
          }
        }
      }
      mm[i] = dp2[c][(1 << c) - 1];
    }
    //pr(i, mm[i]);
  }
  boost;
  dp[0][0] = 1;
  rep(i, 1, 5002) {
    rep(j, 0, 511) { //prev was j.
      //for each remaining ..
      int x = 511 ^ j;
      for(int k = x; ; k = (k - 1)&x) {
        dp[i][k] += mm[511 ^ (j | k)] * dp[i - 1][j];
        if(dp[i][k] >= mod) {
          dp[i][k] -= mod;
        }
        if(k == 0) {
          break;
        }
      }
    }
  }
  tcase {
    int n;
    cin >> n;
    cout << dp[n][0] << endl;
  }
  return 0;
}