说明

Anon作为海归高知，非常喜欢数学，有一天，她学到了\textit{费马平方和定理}，该定理如下：

\textit{对于任意素数$p$，存在两个正整数$a$和$b$，使得$a^2+b^2=p$, 当且仅当$p\equiv 1\pmod 4$或$p=2$}

Anon第二天和Soyo分享了这个定理，Soyo却反过来询问Anon："对于任意的数字$n$，什么时候可以被分解为两个正整数的平方和？"
Anon经过一夜的苦思冥想，并借助GPT的帮助，终于知道了什么时候$n$可以被分解平方和，次日Anon要面对Soyo的$q$次提问，每次询问一个数$n$，Anon只需要回答"Yes"或"No"表示该数是否可以被分解为平方和，而Anon觉得这个问题太简单了，就将这份任务交给你了。

正式描述如下：给出$q$个询问，第$i$次给出一个\bf{正整数}$n_i$，你需要确定是否存在两个\bf{正整数}$a,b$使得$a^2+b^2=n_i$，输出"Yes"或"No"表示是否可以被分解为\bf{两个正整数的平方和}。

请使用较快的输入输出方式。

例如：如果你使用的是cin/cout，请在main函数开头加入以下代码以加速输入输出：

ios::sync_with_stdio(nullptr); cin.tie(nullptr); cout.tie(nullptr);

输入格式

第一行包括一个正整数$q(1\leq q\leq 10^6)$，表示询问的次数。
接下来的$q$行，第$i$行包括一个正整数$n_i(1\leq n_i\leq 2\times 10^7)$，表示第$i$次询问的数。

输出格式

输出$q$行，第$i$行输出Yes或No，表示$n_i$是否能被分解为\bf{两个正整数的平方和}

样例

10
1
2
3
4
5
6
7
8
9
10

No
Yes
No
No
Yes
No
No
Yes
No
Yes

提示

对于样例，可以发现$2=1^2+1^2$，$5=1^2+2^2$，$8=2^2+2^2$，$10=1^2+3^2$，而其余剩余的都不能被分解为\bf{两个正整数的平方和}。

注意，要求是分解成正整数的平方和，因此$1$不能被分解为$1^2+0^2$

注：$p\equiv 1\pmod 4$ 表示$p$除$4$的余数为$1$