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
import math

def is_sum_of_powers(x):
    a_b_max = max(int(math.sqrt(x)) + 1, 3)
    for a in xrange(1, a_b_max):
        #print 'a=%s' % a
        a_square = a**2
        for b in xrange(a, a_b_max):
            b_square = b**2
            if a_square + b_square > x:
                break
            #print 'b=%s' % b
            a_power = a
            for m in xrange(2, a_b_max):
                if a <= 1 and m > 2:
                    break
                a_power *= a
                if a_power + b_square > x:
                    break
                #print 'm=%s' % m
                b_power = b
                for n in xrange(2, a_b_max):
                    if b <= 1 and n > 2:
                        break 
                    #print 'n=%s' % n
                    b_power *= b
                    total = a_power + b_power
                    if total > x:
                        break
                    elif total == x:
                        #print '{a}**{m} + {b}**{n} = {x}'.format(**locals())
                        return True
    return False        
    
def main():             
    no_of_test = int(raw_input())
    for i in xrange(no_of_test):
        x = int(raw_input())
        print "Yes" if is_sum_of_powers(x) else "No"
        
main()