sum-of-powers-27

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
Tags: Dynamic programming


Solutions:
import math
for _ in range(int(input())):
	x=int(input())
	li=[]
	for i in range(2,int(math.sqrt(x))+1):
		for j in range(2,int(math.log(x)/math.log(i))+1):
			li.append(i**j)
	li.append(1)
	li=set(li)
	for i in li:
		if x-i in li:
			print("Yes")
			break;
	else:
		print("No")
			


from sys import stdin
a = [1]
hi = 1000000
for i in range(2,10001):
	if i**2 > hi:
		break
	for j in range(2,46):
		if i**j > hi:
			break
		a.append(i**j)

di = {}
for i in a:
	di[i] = 1
t = stdin.readline()
a = stdin.readlines()
for i in a:
	x = int(i)
	ans = "No"
	for j in di:
		if di.get(x-j,0):
			ans = "Yes";break
	print(ans)