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
from sys import stdin
s = set()
s.add(1)
for i in xrange(2,1001):
	j = 2
	while True:
		if i**j > 10**6:
			break
		s.add(i**j)
		j+=1
s = list(s)
s.sort()
dp = [0]*(10**6 + 5)
dp[0] = 1
for i in s:
	for j in s:
		if i + j > 10**6:
			break
		dp[i+j] = 1
t = int(stdin.readline())
for _ in xrange(t):
	n = int(stdin.readline())
	if dp[n]:
		print 'Yes'
	else:
		print 'No'