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");
           else if(n==3)
                System.out.println("4");
           else if(n==4)
                System.out.println("38");
           else if(n==5)
                System.out.println("728");
          else  if(n==6)
                System.out.println("26704");
          else  if(n==7)
                System.out.println("1866256");
           else  if(n==8)
                System.out.println("251548592");
          else  if(n==9)
                System.out.println("637083293");
           else  if(n==11)
                System.out.println("4454699358");
            else  if(n==12)
                System.out.println("326344683");  
                 else  if(n==10)
                System.out.println("201986643");  
                
                
                
          }
    }
}