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: UNKNOWN_DIFFICULTY

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


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())
		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


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

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))


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


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


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))