#include<bits/stdc++.h>
#define int long long
using namespace std;
auto IN = freopen("diary.in", "r", stdin);
auto OUT = freopen("diary.out", "w", stdout);
auto mread = [](){int x;scanf("%lld", &x);return x;};
const int N = 2005, MOD = 1997;
int t = mread(), c[N][N];
signed main(){
    c[0][0] = 1;
    for(int i = 1; i < N; i ++){
        for(int j = 0; j < N; j ++){
            if(j == 0){
                c[i][j] = 1;
            }
            else{
                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
            }
        }
    }
    while(t --){
        int n = mread();
        if(n & 1){
            printf("0\n");
            continue;
        }
        int ans = 0;
        for(int i = 0; i <= n; i += 2){
            (ans += c[n][i >> 1] * c[n - (i >> 1)][i >> 1] * c[n - i][n - i >> 1] * c[n - i - (n - i >> 1)][n - i >> 1] % MOD) %= MOD;
        }
        printf("%lld\n", ans);
    }
    return 0;
}