Problem Statement

square1001 has decided to define a number that can be expressed as the $k$-th power of a prime ($k$ is a positive integer) as an "important and powerful number".

You are given a positive integer $N$. Determine whether there exists a combination of primes $p, q$ and positive integers $a, b$ such that $N=p^a + q^b$.
In other words, determine whether $N$ can be expressed as the sum of $2$ "important and powerful numbers".

Note that there are $Q$ test cases, and the number for the $i$-th test case is $N_i$.

Input

$Q$
$N_1$
$N_2$
 :
$N_Q$

The $1$st line contains an integer $Q \ (1 \le Q \le 200)$.
The $i+1$-th line contains an integer $N_i \ (1 \le N_i \le 10^{18})$.

Output

On the $i$-th line, output Yes if there exists a combination $(p, q, a, b)$ such that $N_i = p^a + q^b$, and No otherwise.

Sample

2
251
149

Yes
No