Description

叔叔教自己家孩子学习素数，孩子现在已经知道素数的定义，那叔叔现在出题，问孩子,如果给你个素数，你是否能判断有任意的两个平方数之和等于所给的素数。（建议用scanf进行输入）

Format

Input

第一行输入n，表示有n个待判断的素数，第二行输入n个素数a[0]、a[1].......a[n-1]

(1<= n <= 10^6 ) ( 0 < a[i] < 10^6 )

Output

请判断每个数是否符合任意的两个平方数之和，如果符合输出“YES”，否则“NO”。

Samples

4
5 17 71 193

YES
YES
NO
YES

Hint

这是叔叔的提示

5：5-1^2=4=2^2；

17：17-1^2=16=4^2；

71：找不到两个平方数可以等于71

193：193-1^2=192 193-2^2=189 193-3^2=184 193-4^2=177 …… 193-7^2=144=12^2