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 a^m + b^n = 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
t=int(input())
arr=[0]*1000001
arr[1]=1
for i in range(2,1000):
	x=i*i
	while(x<1000001):
		arr[x]=1
		x*=i
	
while(t>0):
	n=int(input())
	
	f=0
	for i in range(1,1000001):
		if(arr[i]==1):
			if(n>i):
				if(arr[n-i]==1):
					f=1
					print "Yes"
					break
			else:
				print "No"
				f=1
				break
	if(f==0):
		print "No"
	t-=1