Asmany strings are strings of '0's and '1's that have as many 00 as 11. A string such as 00110001 consists of 3 "00" and
1 "11". Of course this is not an Asmany string. 0011, 1100, 000111000111 are Asmany strings. An L'th Asmany number is the number of
Asmany strings of length L for all positive integers L.

For esoteric purposes Chef had an oracle (a device) that was capable of answering whether a number that he entered was an Asmany number.
The problem is that his oracle takes too long for large numbers. Him being Chef, he wants to ask the oracle very
large numbers! You tell him that you can give him a better oracle (a program) that will tell him what he wants to know in the blink of
an eye.

------ Input ------ 

The first Line contains a single number T, the number of test cases.

Each test case contains 1 positive integer N, with not more than 1000 digits.

------ Output ------ 

Print YES if N is an Asmany number, NO otherwise.

------ Constraints ------ 

1 ≤ T ≤ 100
1 ≤ Number of digits in N ≤ 1000

------ Sample Input ------ 

2
3
4

------ Sample Output ------ 

NO
YES

------ Explanation ------ 

4 is an Asmany number. To be precise, it is the 4th Asmany number: There are 4 Asmany strings of length 4. 0011, 1100, 0101, 1010.

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming

Sorting

Mathematics

Complete search


Solutions:
A = [1]
k = 1
for n in range(2, 3328):
	if n & 1:
		k += 1
		A.append(A[-1] + A[-1] * (n - k) // k)
	else:
		A.append(A[-1] + A[-1] * k // (n - k))
Anums = set(A)
T = int(input())
for _ in range(T):
	cand = int(input())
	if cand & 1:
		print('NO')
	else:
		cand //= 2
		print('YES' if cand in Anums else 'NO')


curi = 0
x = 1
curcat = 1
curd = 2
t = int(input())
itera = 0
lst = [2]
for i in range(3333):
	itera += 1
	if x == 1:
		curd = (curd - curcat) * 2
		curcat = curcat * (2 * curi + 1) * (2 * curi + 2) // ((curi + 1) * (curi + 2))
		curi += 1
	else:
		curd = curd * 2
	x = 1 - x
	lst.append(curd)
for i in range(t):
	cur_s = int(input())
	if cur_s <= 1:
		print('NO')
		continue
	l = 0
	r = len(lst) - 1
	while l < r - 1:
		m = (l + r) // 2
		if lst[m] <= cur_s:
			l = m
		else:
			r = m
	if lst[l] == cur_s:
		print('YES')
	else:
		print('NO')