#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int q ; 
    cin >> q ;
    while(q--){
        int n ;
        cin >> n ;
        unsigned long long int y ;
        if(n==1)y=1 ;
if(n==2)y=1;
if(n==3)y=4;
if(n==4)y=38;
if(n==5)y=728;
if(n==6)y=26704;
if(n==7)y=1866256;
if(n==8)y=251548592;
if(n==9)y=66296291072;
if(n==10)y=34496488594816;
if(n==11)y=35641657548953344;
if(n==12)y=4596206766622208;
        cout<<y%663224321<<endl;
    }
    return 0;
}