問題文

square1001は、素数の $k$ 乗 ($k$ は正の整数) で表されるような数を「重要で力のある数」と定義することにしました。

正の整数 $N$ が与えられます。$N=p^a + q^b$ となるような素数 $p, q$ と正の整数 $a, b$ の組み合わせが存在するか判定しなさい。
すなわち、$N$ が $2$ つの「重要で力のある数」の和で表すことができるか判定しなさい。

ただし、テストケースが $Q$ 個あるので、$i$ 番目のテストケースの数を $N_i$ とします。

入力

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

$1$ 行目には、整数 $Q \ (1 \le Q \le 200)$ が一行に与えられます。
$i+1$ 行目には、整数 $N_i \ (1 \le N_i \le 10^{18})$ が一行に与えられます。

出力

$i$ 行目には、$N_i = p^a + q^b$ となるような $(p, q, a, b)$ の組み合わせが存在するならばYes, そうでないならばNoと出力しなさい。

サンプル

2
251
149

Yes
No