sum-of-powers-32

You need to find if a number can be expressed as sum of two perfect powers. That is, given x find if there exists non negative integers a, b, m, n such that am + bn = x.

Input

First line of the input contains number of test cases T. It is followed by T lines, each line contains a sinle number x.

Output

For each test case, print "Yes" (without quotes) if the number can be expressed as sum of two perfect powers. Otherwise print "No" (without quotes).

Constraints

1 ≤ T ≤ 1000

1 ≤ x ≤ 1000000

m > 1, n > 1

SAMPLE INPUT
5
5
15
9
77
100

SAMPLE OUTPUT
Yes
No
Yes
No
Yes

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
t = int(input().strip())
 
 
P = [0]* 1000001
 
for i in range(2, 1000+1):
	j = 2
	while int(pow(i, j)) <= 1000000:
		pos = int(pow(i, j))
		P[pos] = 1
		j+=1
 
P[1] = 1
 
while t:
	t-=1
	
	x = int(input().strip())
	
	f = 0
	for i in range(1, (x>>1)+1):
		if P[i] and P[x-i]:
			f = 1
			break
		
	if f:
		print("Yes")
	else:
		print("No")


P = [0] * 1000001
P[1] = 1 
for i in range(2, 1001):
	j = 2
	while int(pow(i, j)) <= 1000000:
		pos = int(pow(i, j))
		P[pos] = 1
		j += 1

for _ in range(int(input())):
	x = int(input())
	found = False
	for i in range(1, x+1):
		if P[i] and P[x-i]:
			found = True
			break
	print("Yes" if found else "No")