So the Chef has become health conscious and is now lifting weights at the gym. But its his first time so the trainer gives him a simple job to do. 

He has been given a weight lifting rod and N heavy weights, each weighing 20, 21, .... , 2n-1. He has to stick each of the "N" weights on the rod, one after another, in such a way that the right side is never heavier than the left side. At each step he chooses one of the weights that has not yet been fixed on the rod, and fix it on either the left side of the rod or the right, until all of the weights have been placed.

Now help the chef and find out, in how many ways the chef can accomplish this?

-----Input-----
First line of input contains an integer T, the number of test cases. Then T test cases follow. Each line of test case contains one integer, N denoting the number of weights

-----Output-----
The output contains T lines, each containing an integer denoting all possible combinations

-----Example-----
Input:
3
2
5
18

Output:
3
945
221643095476699771875

Difficulty: interview

Starter code:

Solutions:
t = int(input())

while(t>0):
 
 n=int(input())
 if(n<=0):
  print(0)
 
 fact=1
 start=1
 for i in range(1,n+1):
  fact*=start
  start+=2
 print(fact)
 
 t=t-1


#!/usr/bin/env python

'''
from sys import stderr

def f(maxG, remaining):
    #stderr.write('%s %s\n' % (maxG, remaining))
    if not remaining: return 1
    S = 0
    for i in xrange(len(remaining)):
     if remaining[i] < maxG:
     S += 2 * f(maxG, remaining[:i] + remaining[i+1:])
     else:
     S += 1 * f(remaining[i], remaining[:i] + remaining[i+1:])
    return S
'''

def process(N):
 P = 1
 for i in range(1, 2 * N, 2):
  P *= i
 return P

def main():
 T = int(input())
 for t in range(T):
  N = int(input())
  #stderr.write(('*'*70) + '\n')
  #print f(-1, range(N))
  print(process(N))

main()



N=input()
n=int(N)
a=[]
while n>0:
 a.append(input())
 n=n-1
i=0
for value in a:
 a[i]=int(value)
 i=i+1
b=[1,3]
i=2
k=5
while i<100:
 b.append(b[i-1]*k)
 k=k+2
 i=i+1
i=0
n=int(N)
while n>0:
 print(b[a[i]-1])
 i=i+1
 n=n-1

t = eval(input())
i=1
while(i<=t):
  j=eval(input())
  j=(2*j)-1
  k=1
  p=1
  while(k<=j):
    p=p*k
    k=k+2 
  print(p)
  print("\n")
  i=i+1


def comb (i) :
 res = 1
 for k in range(1,i,2) :
  res =res * k
 print(res)
 
t = eval(input())
for i in range( 1 , t + 1 ) :
 h= eval(input())
 h= h+1 
 comb(2*h-1)


t=int(input())
while t>0:
 n=int(input())
 ans=1
 temp=1
 while temp<=n :
  ans=ans*(2*temp-1)
  temp=temp+1
 print(ans)
 t=t-1

import sys

N=80
ans=[1]
i=1
while i < N:
 ans.append(ans[i-1] * (2*i-1))
 i = i+1

T=int(sys.stdin.readline().strip())
while T > 0:
 n=int(sys.stdin.readline().strip())
 print(ans[n])
 T=T-1;


N=eval(input())
n=int(N)
a=[]
while n>0:
 a.append(eval(input()))
 n=n-1
i=0
for value in a:
 a[i]=int(value)
 i=i+1
b=[1,3]
i=2
k=5
while i<100:
 b.append(b[i-1]*k)
 k=k+2
 i=i+1
i=0
n=int(N)
while n>0:
 print(b[a[i]-1])
 i=i+1
 n=n-1




dp = [-1 for i in range(11919)]
fac = [1 for i in range(111)]
for i in range(1,100):
 fac[i] = fac[i-1]*i
def comb(n, r):
 return fac[n]/(fac[n-r]*fac[r])
 ret = 1
 for i in range(r):
  ret *= (n-i)
  ret /= (i+1)
 return ret
 # return factorial(n)/(factorial(n-r)*factorial(r))

def solve(n):
 if dp[n] > 0 :
  return dp[n]
 if n == 0:
  return 1
 ans = 0
 for i in range(n):
  ans += comb(n-1, i)*solve(i)*pow(2,n-1-i)*fac[(n-1-i)]
 dp[n] = ans
 return dp[n]

t = int(input())
for i in range(t):
 n = int(input())
 ans = 0
 for i in range(n):
  ans += comb(n-1, i)*solve(i)*pow(2,n-1-i)*fac[(n-1-i)]
 print(ans)
 


testcases = int(input())
while testcases:
 p = int(input())
 Res = 1;
 n = 1;
 while n <= (2*p):
  Res = Res*n
  n = n+2
 print(Res)
 testcases=testcases-1


def dfac ( n ) :
 ans = 1
 for i in range(1,n,2) :
  ans = ans * i
 print(ans)
 
t = eval(input())
for i in range( 1 , t + 1 ) :
 n = eval(input())
 n = n+1 
 dfac ( 2 * n - 1 )


import sys

def DFact(n):
 s = 1
 for i in range(3, n + 1, 2):
  s *= i
 return s

T = int(sys.stdin.readline())
for i in range(T):
 N = int(sys.stdin.readline())
 print(DFact(2 * N - 1))


def dfac ( n ) :
 ans = 1
 for i in range(1,n,2) :
  ans = ans * i
 print(ans)

t = eval(input())
for i in range( 1 , t + 1 ) :
 n = eval(input())
 n = n+1 
 dfac ( 2 * n - 1 )

import sys
def fact(x):
 if x==1:
  return 1
 else:
  return x*fact(x-2)
line = sys.stdin.readline()
n=int(line)
while n:
 try:
  line = sys.stdin.readline()
  t=int(line)
 except:
  break
 x=fact((2*t)-1)
 print("%d\n"%x)
 n-=1

''' 
Chef at Gym
Created on Mar 3, 2012

@author: Andy Huang
'''
t = eval(input())
moi = []
ans = 1
mul = 3
i = 75
moi.append(1);
moi.append(1);
while i:
 ans *= mul
 mul += 2
 moi.append(ans)
 i -= 1
while (t):
 n = eval(input())
 print(moi[n])
 t -= 1
#print(moi)


import sys

k=1
l=[]
n=1
while n<=1000:
 l.append(k)
 k=k*(2*n+1)
 n+=1

t = int(input())

for i in range(t):
 n=int(input())
 print(l[n-1])



return


def D(n): return n and (2*n-1)*D(n-1) or 1
def N(n): return n and (4*n*n-8*n+3)*N(n-2)+7*D(n-2) or 1

n=eval(input())
for i in range(n):
 n = eval(input())
 print(D(n))


def D(n): return n and (2*n-1)*D(n-1) or 1
def N(n): return n and (4*n*n-8*n+3)*N(n-2)+7*D(n-2) or 1

n=eval(input())
for i in range(n):
 n = eval(input())
 print(D(n))