import java.util.*;
public class Main {
    static int n;
    static int cnt=0;
    static int o[]= {1,-1};
    static int []f=new int[100];
    static void dfs(int k,int l) {
        if(l==n) {
            cnt++;
            return;
        }
        for(int i=0;i<2;i++) {
            int kk=(n+o[i]*l+k)%n;
            if(f[kk]==0) {
                f[kk]=1;
            dfs(kk,l+1);
            f[kk]=0;
            }
        }
    }
  public static void main(String[] args){
      Scanner in=new Scanner(System.in);
      int T=in.nextInt();
      while(T-->0) {
          n=in.nextInt();
          cnt=0;
          f=new int[100];
          f[0]=1;
          dfs(0,1);
          System.out.println(cnt);
      }
   }
}