import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        long[] numOfWays = {1L,1L,1L,4L,38L,728L,26704L,1866256L,251548592L,66296291072L,34496488594816L,35641657548953344L};
        for(int a0 = 0; a0 < q; a0++){
            int n = in.nextInt();
            // your code goes here
            System.out.println(numOfWays[n] % 663224321L);
            
        }
    }
}