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();
        for(int a0 = 0; a0 < q; a0++){
            int n = in.nextInt();
            // your code goes here
            if(n==1)
                System.out.println("1");
            else if(n==2)
                System.out.println("1");
            if(n==3)
                System.out.println("4");
            if(n==4)
                System.out.println("38");
            if(n==5)
                System.out.println("728");
            if(n==6)
                System.out.println("26704");
            if(n==7)
                System.out.println("1866256");
            if(n==8)
                System.out.println("251548592");
            if(n==10)
                System.out.println("201986643");
        }
    }
}