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

public class Solution 
{
public int fact(int x)
    {
    int f=1;
    for(int i=1;i<=x;i++)
        f*=i;
    return f;
}
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Solution ob = new Solution();
        int q = in.nextInt();
        for(int a0 = 0; a0 < q; a0++){
            int n = in.nextInt();
            // your code goes here
            
            long c = (long)(n*(n-1)/2);
            long p = (long)Math.pow(2,c);
            long t = n*p;
            long f = ob.fact(n);
            long x = (long)(t/f);
            long r = x%663224321;
            System.out.println(r);
        }
    }
}