sum-of-powers-30

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 am + bn = 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

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: