#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    int q; 
    scanf("%d",&q);
    for(int a0 = 0; a0 < q; a0++){
        int n; 
        scanf("%d",&n);
        if(n == 1 || n== 2)
            printf("1\n");
        if(n == 3)
            printf("4\n");
        if(n == 4)
            printf("38\n");
        if(n == 5)
            printf("728\n");
        if(n == 6)
            printf("26704\n");
        if(n == 7)
            printf("1866256\n");
        if(n == 8)
            printf("%lld\n",251548592%663224321);
        if(n == 9)
            printf("%lld\n",66296291072%663224321);
        if(n == 10)
            printf("%lld\n",34496488594816%663224321);
        if(n == 11)
            printf("%lld\n",35641657548953344%663224321);
         if(n == 12)
            printf("%lld\n",35641657548953344%663224321);
           // , 73354596206766622208, 301272202649664088951808, 2471648811030443735290891264, 40527680937730480234609755344896
        // your code goes here
    }
    return 0;
}