#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ZERO (1e-10)
#define INF (1<<29)
#define CL(A,I) (memset(A,I,sizeof(A)))
#define DEB printf("DEB!\n");
#define D(X) cout<<"  "<<#X": "<<X<<endl;
#define EQ(A,B) (A+ZERO>B&&A-ZERO<B)
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
#define IN(n) int n;scanf("%d",&n);
#define FOR(i, m, n) for (int i(m); i < n; i++)
#define F(n) FOR(i,0,n)
#define FF(n) FOR(j,0,n)
#define FT(m, n) FOR(k, m, n)
#define aa first
#define bb second
void ga(int N,int *A){F(N)scanf("%d",A+i);}
struct big{
    static const ll MM=999999999;
    ll l,a[1024];
    big(int A=0):l(1){a[0]=A;}
    bool eq(int h){return l==1&&a[0]==h;}
    void operator=(int h){*a=h,l=1;}
    void operator+=(int a){add(a,0);}
    void operator+=(big &b){F(b.l)add(b.a[i],i);}
    void add(ll s,int nd){
        if(nd==l)a[l++]=0;
        a[nd]+=s;
        if(a[nd]>MM)a[nd]-=MM+1,add(1,nd+1);
    }
    ll rem(int u,ll r,ll d){return ~u?rem(u-1,(a[u]+(MM+1)*r)%d,d):r;}
    ll operator%(ll d){return rem(l-1,0,d);}
    void operator++(){add(1,0);}
    void operator--(){
        int L(0);
        while(!a[L])a[L++]=MM;
        --a[L];
    }
    void div(int u,ll r,ll d){
        if(!~u)return;
        ll h(a[u]+(MM+1)*r);
        div(u-1,h%d,d);
        a[u]=h/d;
    }
    void operator/=(ll d){
        div(l-1,0,d);
        while(l>1&&!a[l-1])--l;
    }
    big(const big&r):l(r.l){F(l)a[i]=r.a[i];}
    void pow(int k){
        if(!k){l=1;a[0]=1;return;}
        big n(*this),N(n);--k;
        while(k){
            if(k&1)*this*=n;
            n*=N,k>>=1,N=n;
        }
    }
    void operator*=(big &b){
        static ll A[1024];
        ll L(l);
        l+=b.l-1;
        F(L)A[i]=a[i];
        F(l)a[i]=0;
        F(b.l)FF(L)
            if((a[i+j]+=A[j]*b.a[i])>MM)
                add(a[i+j]/(MM+1),i+j+1),a[i+j]%=MM+1;
    }
    void operator*=(unsigned k){
        F(l)a[i]*=k;
        for(int i(l-1);~i;--i)
            if(a[i]>MM)add(a[i]/(MM+1),i+1),a[i]%=MM+1;
    }
    void prt(void){
        printf("%lld",a[l-1]);
        for(int i(l-2);~i;--i)
            printf("%09lld",a[i]);
    }
    int prt(char*c){
        sprintf(c,"%lld",a[l-1]);
        int L(strlen(c));
        for(int i(l-2);~i;--i)
            sprintf(c+L,"%09lld",a[i]),L+=9;
        return L;
    }
    bool operator<(int A)const{return l==1&&*a<A;}
    bool operator>(int A)const{return l>1||*a>A;}
    bool operator<(const big&r)const{
        if(r.l!=l)return l<r.l;
        F(l)if(a[l-i-1]!=r.a[l-i-1])return a[l-i-1]<r.a[l-i-1];
        return 0;
    }
    bool operator>(const big&r)const{
        if(r.l!=l)return l>r.l;
        F(l)if(a[l-i-1]!=r.a[l-i-1])return a[l-i-1]>r.a[l-i-1];
        return 0;
    }
    bool operator==(const big&r)const{
        if(r.l!=l)return 0;
        F(l)if(a[l-i-1]!=r.a[l-i-1])return 0;
        return 1;
    }
    void sub(ll s,int nd){
        a[nd]-=s;
        if(!a[nd]&&l==nd)--l;
        else if(a[nd]<0)a[nd]+=MM+1,sub(1,nd+1);
    }
    void operator-=(big&r){
        F(r.l)sub(r.a[i],i);    
		while(l>1&&!a[l-1])--l;
    }
    void mm(big&b,int k,int m){
        CL(a,0),l=b.l+m;
        ll c(0);
        F(b.l)c+=b.a[i]*k,a[i+m]=c%(MM+1),c/=(MM+1);
        while(c)a[l++]=c%(MM+1),c/=(MM+1);
    }
    void operator/=(big&b){
        big t,x(*this);
        if(x<b){*this=0;return;}
        //if(x==b){*this=1;return;}
        CL(a,0),l-=b.l-1;
        for(int i(l-1);~i;--i)for(ll k(1ll<<29);k;k>>=1){
            t.mm(b,k,i);
            if(!(x<t))x-=t,a[i]+=k;
            if(a[i]>MM)add(a[i]/(MM+1),i+1),a[i]%=(MM+1);
        }
        while(l>1&&!a[l-1])--l;
    }
    void st(int u,char *c,int L){
        a[u]=0;l=u+1;
        F(L)a[u]*=10,a[u]+=c[i]-'0';
    }
    bool scan(void){
        static char c[1024];
        if(!~scanf("%s",c))return 0;
        return scan(c),1;
    }
    void scan(char*c){
        int L(strlen(c)),I(0);
        while(L>0)st(I++,c+L-(L>=9?9:L),(L>=9?9:L)),L-=9;
    }
    big operator%(big&b){
        big t,x(*this);
        for(int i(l-b.l);~i;--i)for(int k(1<<29);k;k>>=1){
            t.mm(b,k,i);
            if(!(x<t))x-=t;
        }
        return x;
    }
    big gcd(big&b){
        big A(*this),B(b),C;
        if(B<A)swap(A,B);
        while(!A.eq(0))C=A,A=B%A,B=C;
        return B;
    }
    big operator*(big b){
        b*=*this;
        return b;
    }
    big operator+(big b){
        b+=*this;
        return b;
    }
    big operator-(big b){
        big A(*this);
        A-=b;
        return A;
    }
}B;
#define MOD 663224321
ll T[]={1,1,1,4,38,728,26704,1866256,251548592,637083293,201986643,445470011,383172888,385948552,65297001,308964152,295903622,464669423,421784373,524744930,421609377,396525952,331634053,621426071,161054976,238301041,452783023,422192490,190939721,230611583,619340159,31552273,657817831,508936313,335225631,525083904,645124959,441298877,641956910,68492278,578356264,273843232,563473827,403219431,331758921,151880747,440853404,517749504,634441325,537132076,357914721};
int N;
int main(void){
//    F(51)B.scan(),printf("\"%lld\",\n",B%MOD);
    IN(_)F(_)scanf("%d",&N),assert(N<52),printf("%lld\n",T[N]);
    return 0;
}