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
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import math 
def s(n):
    t = set()
    t.add(1)
    for i in xrange(2, int(math.sqrt(n)) + 1):
        u = i * i
        while u < n:
            t.add(u)
            u *= i
    for i in t:
        if n - i in t:
            return 'Yes'
    return 'No'
 
T = int(raw_input())
for i in xrange(T):
	n = int(raw_input())
	print s(n)