We have N persons sitting on a round table. Any person can do a handshake with any other person. 
     1
2         3
     4
Handshake with 2-3 and 1-4 will cause cross.
In how many ways these N people can make handshakes so that no two handshakes cross each other. N would be even.  
 
Example 1:
Input:
N = 2
Output:
1
Explanation:
{1,2} handshake is
possible.
Example 2:
Input:
N = 4
Output:
2
Explanation:
{{1, 2}, {3, 4}} are the
two handshakes possible.
{{1, 3}, {2, 4}} is another
set of handshakes possible.
Your Task:
You don't need to read input or print anything. Your task is to complete the function count() which takes an integer N as input parameters and returns an integer, the total number of handshakes possible so that no two handshakes cross each other.
 
Expected Time Complexity: O(2^{N})
Expected Space Complexity: O(1)
 
Constraints:
1 <= N <= 30

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Complete search

Starter code: #User function Template for python3

class Solution:
    def count(self, N):
        # code here

Solutions:
class Solution:

	def count(self, N):

		def findCatalan(x):
			if x == 0 or x == 1:
				return 1
			result = 0
			for i in range(0, x):
				result += findCatalan(i) * findCatalan(x - i - 1)
			return result
		return findCatalan(N // 2)


class Solution:

	def count(self, N):
		dp = [0] * (N // 2 + 1)
		dp[0] = 1
		for i in range(1, len(dp)):
			for j in range(i):
				dp[i] += dp[j] * dp[i - 1 - j]
		return dp[N // 2]


class Solution:

	def count(self, N):
		if N % 2 == 1:
			return 0
		dp = [1] * (N + 1)
		for i in range(4, N + 1):
			(tmp, M) = (0, i - 2)
			for j in range(0, M // 2, 2):
				tmp += dp[j] * dp[M - j]
			tmp *= 2
			if M % 4 == 0:
				tmp += dp[M // 2] * dp[M // 2]
			dp[i] = tmp
		return dp[N]


def rec(N, dp):
	if N == 0:
		return 1
	if N % 2:
		return 0
	if N in dp:
		return dp[N]
	ans = 0
	for i in range(2, N + 1):
		ans += rec(i - 1 - 1, dp) * rec(N - i, dp)
	dp[N] = ans
	return ans

class Solution:

	def count(self, N):
		dp = {}
		return rec(N, dp)


d = {0: 1, 2: 1, 4: 2}

class Solution:

	def count(self, N):
		if N % 2 != 0:
			N -= 1
		if N in d:
			return d[N]
		ans = 0
		for j in range(1, N, 2):
			ans += self.count(j - 1) * self.count(N - j - 1)
		return ans


class Solution:

	def count(self, N):
		result = 0
		if N % 2 == 1:
			return 0
		elif N == 0:
			return 1
		for i in range(0, N, 2):
			result += self.count(i) * self.count(N - 2 - i)
		return result


def hand(N):
	if N <= 2:
		return 1
	ans = 0
	for i in range(0, N, 2):
		ans += hand(i) * hand(N - i - 2)
	return ans

class Solution:

	def count(self, N):
		ans = hand(N)
		return ans


class Solution:

	def solve(self, N, dict_hand):
		if N <= 2:
			return 1
		if N in dict_hand:
			return dict_hand[N]
		ans = 0
		for i in range(0, N, 2):
			ans += self.solve(i, dict_hand) * self.solve(N - i - 2, dict_hand)
			dict_hand[N] = ans
		return ans

	def count(self, N):
		dict_hand = {2: 1}
		self.solve(N, dict_hand)
		return dict_hand[N]


class Solution:

	def count(self, N):
		if N & 1:
			return 0
		if N == 0:
			return 1
		total = 0
		for i in range(N):
			total += self.count(i) * self.count(N - i - 2)
		return total


class Solution:

	def count(self, N):
		d = {}

		def helper(x):
			if x == 0 or x == 1:
				return 1
			if x in d:
				return d[x]
			ans = 0
			for i in range(x):
				ans += helper(i) * helper(x - i - 1)
			d[x] = ans
			return d[x]
		return helper(N // 2)


class Solution:

	def count(self, N):
		if N % 2 == 1:
			return 0
		kMod = 1000000007
		dp = [0] * (N + 1)
		dp[0] = 1
		for i in range(2, N + 1):
			for j in range(2, i + 1, 2):
				dp[i] += dp[j - 2] * dp[i - j] % kMod
		return dp[-1] % kMod


class Solution:

	def count(self, n):
		if n == 0:
			return 1
		ans = 0
		for i in range(0, n, 2):
			ans += self.count(i) * self.count(n - 2 - i)
		return ans


class Solution:

	def count(self, N, dic={}):
		if N == 0:
			return 1
		if N in dic:
			return dic[N]
		res = 0
		for i in range(0, N, 2):
			res += self.count(i, dic) * self.count(N - i - 2, dic)
		dic[N] = res
		return dic[N]


from collections import defaultdict

class Solution:
	hmap = defaultdict(int)

	def __init__(self):
		self.hmap[0] = 1

	def count(self, n):
		if n in self.hmap:
			return self.hmap[n]
		for i in range(0, n, 2):
			self.hmap[n] += self.count(i) * self.count(n - i - 2)
		return self.hmap[n]


class Solution:

	def count(self, N):

		def catalan(n):
			dp = [0] * (n + 1)
			dp[0] = 1
			for i in range(1, n + 1):
				dp[i] = 0
				for j in range(i):
					dp[i] += dp[j] * dp[i - j - 1]
			return dp[n]
		return catalan(N // 2)


def handShake(p):
	dp = [0 for _ in range(p + 1)]
	dp[0] = dp[1] = 1
	for i in range(2, p + 1, 2):
		for j in range(0, i - 1, 2):
			dp[i] += dp[j] * dp[i - 2 - j]
	return dp[-1]

class Solution:

	def count(self, N):
		return handShake(N)


class Solution:

	def count(self, N):
		return self.catalan(N // 2)

	def catalan(self, n):
		if n <= 1:
			return 1
		res = 0
		for i in range(n):
			res += self.catalan(i) * self.catalan(n - i - 1)
		return res


class Solution:

	def helper(self, x):
		if x == 0 or x == 1:
			return 1
		res = 0
		for i in range(x):
			a = self.helper(i)
			b = self.helper(x - i - 1)
			res += a * b
		return res

	def count(self, N):
		res = self.helper(N // 2)
		return res


class Solution:

	def count(self, N):
		dp = [0] * (N + 1)
		dp[0] = 1
		dp[1] = 1
		for i in range(2, N + 1):
			for j in range(i):
				dp[i] += dp[j] * dp[i - j - 1]
		return dp[N // 2]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.count(N))


class Solution:

	def count(self, N):

		def num_handshakes(n):
			if n % 2 == 1:
				return 0
			elif n == 0:
				return 1
			res = 0
			for i in range(0, n, 2):
				res += num_handshakes(i) * num_handshakes(n - 2 - i)
			return res
		return num_handshakes(N)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.count(N))


class Solution:

	def count(self, N):
		a = [-1] * (N + 1)
		ans = 0
		for i in range(0, N + 1):
			if i % 2 != 0:
				a[i] = 0
		a[0] = 0
		if N == 1 or N == 0:
			return 0
		a[2] = 1
		if N == 2:
			return 1
		a[4] = 2
		if N < 6:
			return a[N]
		for i in range(6, N + 1):
			if a[i] == -1:
				for k in range(2, i + 1):
					if a[k - 2] == 0 or a[i - k] == 0:
						ans += a[k - 2] + a[i - k]
					else:
						ans += a[k - 2] * a[i - k]
				a[i] = ans
				ans = 0
		return a[N]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.count(N))


class Solution:

	def count(self, N):
		if N % 2 != 0:
			return 0
		n = N // 2
		if n < 3:
			return n
		a = [1, 1, 2]
		for i in range(3, n + 1):
			p = 0
			for j in range(i):
				p += a[j] * a[i - j - 1]
			a.append(p)
		return a[-1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.count(N))


class Solution:

	def count(self, N):
		Dict = {}

		def findCount(n, Dict):
			if n == 0 or n == 1:
				return 1
			count = 0
			for i in range(n):
				if i not in Dict:
					Dict[i] = findCount(i, Dict)
				val1 = Dict[i]
				if n - i - 1 not in Dict:
					Dict[n - i - 1] = findCount(n - i - 1, Dict)
				val2 = Dict[n - i - 1]
				count += val1 * val2
			return count
		return findCount(N // 2, Dict)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.count(N))


class Solution:

	def count(self, N):

		def solution(n):
			catalan = [1] * (n + 1)
			for i in range(2, n + 1):
				catalan[i] = 0
				for j in range(i):
					catalan[i] += catalan[j] * catalan[i - j - 1]
			return catalan[n]
		if N % 2 != 0:
			return False
		else:
			return solution(N // 2)


from functools import lru_cache

class Solution:

	def count(self, n):

		@lru_cache(None)
		def dp(m):
			if m % 2 == 1:
				return 0
			if m == 0:
				return 1
			ans = 0
			for i in range(0, m, 2):
				ans += dp(i) * dp(m - i - 2)
			return ans
		return dp(n)


class Solution:

	def count(self, N):
		p = N // 2
		arr = [0] * (p + 1)
		arr[0] = 1
		arr[1] = 1
		for i in range(2, p + 1):
			for j in range(0, p):
				arr[i] += arr[j] * arr[i - j - 1]
		return arr[p]


class Solution:

	def __init__(self):
		self.ans = 0

	def count(self, n):
		if n == 0 or n == 2:
			return 1
		else:
			a = n - 2
			b = 0
			ans = 0
			while a >= 0:
				ans += self.count(a) * self.count(b)
				a -= 2
				b += 2
		return ans


class Solution:

	def count(self, N):
		if N == 2:
			return 1
		if N == 0:
			return 1
		ans = 0
		left = 0
		right = N - 2
		while left <= N - 2:
			ans += self.count(left) * self.count(right)
			left += 2
			right -= 2
		return ans


class Solution:

	def count(self, N):
		memo = {}

		def dp(n):
			if n == 0:
				return 1
			if n & 1:
				return 0
			if n in memo:
				return memo[n]
			ans = 0
			for i in range(2, n + 1):
				grp1 = i - 2
				grp2 = n - i
				ans += dp(grp1) * dp(grp2)
			return ans
		res = dp(N)
		return res


class Solution:

	def count(self, N):
		if N == 0:
			return 0
		else:
			return int(self.fact(N) / (self.fact(N / 2 + 1) * self.fact(N / 2)))

	def fact(self, n):
		if n == 1:
			return 1
		else:
			return n * self.fact(n - 1)


class Solution:

	def count(self, N):
		arr = [0] * (N + 1)
		arr[0] = 1
		if N == 0:
			return arr[0]
		for i in range(2, N + 1, 2):
			temp = 0
			for j in range(0, i, 2):
				temp = temp + arr[j] * arr[i - 2 - j]
			arr[i] = temp
		return arr[N]


class Solution:

	def count(self, N):
		if N <= 2:
			return 1
		i = N - 2
		sum = 0
		while i >= 0:
			sum += self.count(i) * self.count(N - 2 - i)
			i -= 2
		return sum


from sys import stdin
input = stdin.readline
inp = lambda : list(map(int, input().split()))
mod = 10 ** 9 + 7

def add(a, b):
	return (a % mod + b % mod) % mod

def mul(a, b):
	return a % mod * (b % mod) % mod
dp = [-1 for i in range(501)]

def solve(n):
	if n == 0:
		return 1
	if dp[n] != -1:
		return dp[n]
	ans = 0
	for i in range(n):
		left = solve(i)
		right = solve(n - i - 1)
		ans = add(ans, mul(left, right))
	dp[n] = ans
	return ans

def answer():
	ans = solve(n)
	return ans
for T in range(int(input())):
	n = int(input())
	if n & 1:
		continue
	n //= 2
	print(answer())
exit()


class Solution:

	def count(self, N):
		if N == 0:
			return 0
		if N == 2:
			return 1
		c = 0
		for i in range(0, N - 1, 2):
			left = self.count(i)
			right = self.count(N - 2 - i)
			if left and right:
				c += left * right
			else:
				c += left + right
		return c


class Solution:

	def count(self, N):
		sum1 = 0
		if N == 0 or N == 2:
			return 1
		else:
			for i in range(0, N, 2):
				sum1 = sum1 + self.count(i) * self.count(N - i - 2)
		return sum1


class Solution:

	def count(self, N):
		if N == 0:
			return 1
		ans = 0
		for idx in range(0, N, 2):
			ans += self.count(idx) * self.count(N - 2 - idx)
		return ans


class Solution:

	def count(self, N):
		if N == 0:
			return 1
		answear = 0
		for i in range(0, N, 2):
			ob = Solution()
			answear += ob.count(i) * ob.count(N - 2 - i)
		return answear


class Solution:

	def count(self, N):
		if N % 2 == 1:
			return 0
		elif N == 0:
			return 1
		res = 0
		i = 0
		while i < N:
			res += self.count(i) * self.count(N - 2 - i)
			i += 2
		return res


import math

def catlan(n):
	c = int(math.factorial(2 * n) / (math.factorial(n + 1) * math.factorial(n)))
	return c

class Solution:

	def count(self, N):
		if N % 2 == 1:
			return 0
		else:
			return catlan(int(N / 2))


from math import factorial as fac

class Solution:

	def count(self, N):
		if N % 2 == 1:
			return 0
		return check(N // 2)

def check(n):
	return fac(2 * n) // fac(n + 1) // fac(n)


class Solution:

	def count(self, N):

		def handshakes(min, max):
			total_handshakes = 0
			if min >= max:
				return 1
			for partner in range(min + 1, max + 1, 2):
				above_handshakes = handshakes(min + 1, partner - 1)
				below_handshakes = handshakes(partner + 1, max)
				total_handshakes += above_handshakes * below_handshakes
			return total_handshakes
		return handshakes(1, N)


from collections import defaultdict
d = defaultdict(lambda : 0)
for i in range(6, 32, 2):
	(d[0], d[2], d[4]) = (1, 1, 2)
	res = 0
	for j in range(2, i // 2 + 1):
		res += d[j - 2] * d[i - j]
	res *= 2
	res += d[i // 2 - 1] ** 2
	d[i] = res

class Solution:

	def count(self, N):
		return d[N]