Rupsa really loves triangles. One day she came across an equilateral triangle having length of each side as an integer N. She started wondering if it was possible to transform the triangle keeping two sides fixed and alter the third side such that it still remains a triangle, but the altered side will have its length as an even integer, and the line drawn from the opposite vertex to the mid-point of the altered side is of integral length.
Since Rupsa is in a hurry to record a song for Chef as he really loves her songs, you must help her solve the problem as fast as possible.

-----Input-----
The first line of input contains an integer T denoting the number of test cases.
Each test-case contains a single integer N.

-----Output-----

For each test case, output "YES" if the triangle transformation is possible, otherwise "NO" (quotes for clarity only, do not output).

-----Constraints-----
- 1 ≤ T ≤ 106
- 1 ≤ N ≤ 5 x 106

-----Sub tasks-----
- Subtask #1: 1 ≤ T ≤ 100, 1 ≤ N ≤ 104 (10 points)
- Subtask #2: 1 ≤ T ≤ 104, 1 ≤ N ≤ 106 (30 points)
- Subtask #3: Original Constraints (60 points)

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

Output:YES
NO

-----Explanation-----
- In test case 1, make the length of any one side 6, and it will suffice.

Difficulty: MEDIUM_HARD
Tags: Geometry

Number theory

Mathematics

Starter code:

Solutions:
import math
t = int(input())
for _ in range(t):
	n = int(input())
	count = 0
	for i in range(2, 2 * n, 2):
		h = math.sqrt(n * n - i * i / 4)
		if h.is_integer() == True:
			count += 1
		else:
			count += 0
	if count >= 1:
		print('YES')
	else:
		print('NO')


from sys import stdin
dp = [0] * 5000010

def precompute():
	for i in range(2, 5000010):
		if dp[i] == 0:
			j = i
			if (i - 1) % 4 == 0:
				while j < 5000010:
					dp[j] = 1
					j += i
			else:
				while j < 5000010:
					if dp[j] != 1:
						dp[j] = 10
					j += i
	return
precompute()
t = int(stdin.readline())
for i in range(0, t):
	N = n = int(stdin.readline())
	if dp[N] == 1:
		print('YES')
	else:
		print('NO')


import math
lim = 5000000
mlim = int(math.sqrt(lim) + 2)
hyps = dict()
for m in range(1, mlim, 2):
	prh = m * m
	for n in range(m + 1, 2 * lim, 2):
		prh += 2 * n
		if prh > lim:
			break
		if prh not in hyps:
			for k in range(1, lim // prh + 1):
				hyps[k * prh] = True
out = []
for _ in range(int(input())):
	out.append('YES' if int(input()) in hyps else 'NO')
print(*out, sep='\n')


import math
t = int(input())
for _ in range(0, t):
	n = int(input())
	sides = []
	for i in range(2, n + n):
		if i % 2 == 0 and i != n:
			sides.append(i // 2)
	f = 0
	for i in sides:
		pyt = pow(n, 2) - pow(i, 2)
		if math.sqrt(pyt) - int(math.sqrt(pyt)) == 0.0:
			print('YES')
			f = 1
			break
	if f == 0:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	c = 0
	for j in range(2, n, 2):
		if int((n ** 2 - j ** 2) ** 0.5) == (n ** 2 - j ** 2) ** 0.5:
			c = c or 1
			break
		else:
			c = c or 0
	if c == 1:
		print('YES')
	else:
		print('NO')


import math

def isPos(num):
	if num % 2 == 0:
		for i in range(num, 2 * num, 1):
			if (num ** 2 - (i / 2) ** 2) ** (1 / 2) == int((num ** 2 - (i / 2) ** 2) ** (1 / 2)):
				return 'YES'
		return 'NO'
	else:
		for i in range(num + 1, 2 * num, 1):
			if (num ** 2 - (i / 2) ** 2) ** (1 / 2) == int((num ** 2 - (i / 2) ** 2) ** (1 / 2)):
				return 'YES'
		return 'NO'
test = int(input())
for __ in range(test):
	num = int(input())
	print(isPos(num))


lim = 5000000
hyps = [False] * (lim + 1)
m = -1
while True:
	m += 2
	prh = m * m
	if prh > lim:
		break
	n = m - 1
	while True:
		n += 2
		prh += 2 * n
		if prh > lim:
			break
		if not hyps[prh]:
			for k in range(1, lim // prh + 1):
				hyps[k * prh] = True
out = []
for _ in range(int(input())):
	out.append('YES' if hyps[int(input())] else 'NO')
print(*out, sep='\n')


global primes
global result
result = []
from math import sqrt

def sieve():
	limit = 5 * 10 ** 6 + 7
	prime = [True] * limit
	for i in range(3, int(sqrt(limit)) + 1, 2):
		if prime[i]:
			prime[i * i::2 * i] = [False] * len(range(i * i, limit, 2 * i))
	global primes
	primes = [2] + [i for i in range(3, limit, 2) if prime[i]]

def equi():
	limit1 = 5 * 10 ** 6 + 7
	global result
	result = [False] * limit1
	global primes
	for i in primes:
		if i % 4 == 1:
			result[i] = True
			result[i::i] = [True] * len(range(i, limit1, i))
import sys
sieve()
equi()
t = int(sys.stdin.readline())
for _ in range(t):
	a = int(sys.stdin.readline())
	if result[a]:
		print('YES')
	else:
		print('NO')


t = int(input())
import math
for i in range(t):
	b = []
	n = int(input())
	for p in range(n + 1, 2 * n):
		if p % 2 == 0:
			a = math.sqrt(n ** 2 - (p / 2) ** 2)
			if a - int(a) == 0:
				b.append(i)
	if len(b) == 0:
		print('NO')
	elif len(b) != 0:
		print('YES')


def triples(limit):
	a = [True] * limit
	b = [False] * limit
	a[0] = a[1] = False
	for (i, isprime) in enumerate(a):
		if isprime:
			if (i - 1) % 4 == 0:
				for n in range(i, limit, i):
					b[n] = True
			for n in range(i * i, limit, i):
				a[n] = False
	return b

def solve(N, trip):
	if trip[N]:
		return 'YES'
	else:
		return 'NO'

def main(infile, outfile):
	trip = triples(5000001)
	T = int(infile.readline())
	for t in range(T):
		N = int(infile.readline())
		outfile.write(str(solve(N, trip)) + '\n')
from sys import stdin, stdout
main(stdin, stdout)


maxc = 5 * 10 ** 6
cs = set()
maxp = 1580
for p in range(1, maxp):
	for q in range(p + 1, maxc):
		c = int(p ** 2 + q ** 2)
		if c > maxc:
			break
		if not c in cs:
			cs.update({c * i for i in range(1, maxc // c + 1)})
import sys
input = sys.stdin.readline
print = sys.stdout.write
for t in range(int(input())):
	print('YES\n' if int(input()) in cs else 'NO\n')