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
divi=[]
for i in range(1,1001):
    for j in range(2,21):
        m=pow(i,j)
        if(m>1000000):
            break;
        divi.append(m)
divi=set(divi)
divi=list(divi)
divi.sort()
t=int(raw_input())
for i in range(t):
    num=int(raw_input())
    count=0
    for i in divi:
        if i>num:
            break;
        check=num-i
        if check in divi:
            count=1
            break;
    if count==0:
        print "No"
    else:
        print "Yes"