解题思路

1. 预处理素数

   • 利用埃氏筛在线性或近线性时间求出所有不超过 $\sqrt{10^9}\approx31623$ 的素数，记作列表 $P$

2. 分解与累加 对每个查询的 $n$：

题目内容

小红薯定义一个点赞数$n$为好数，当且仅当这个数的所有本质不同质因子之和为奇数。

• 例如，$12$的本质不同质因子为{$2，3$}，且$2+3=5$为奇数，因此$12$是好数。
• 特别地，当$n=1$时无质因子，本质不同质因子之和视为$0$。

现在，首页上有好多$Plog$，请帮助小红薯判断每条$Plog$的点赞数都是不是好数。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≤T≤10^4)$代表数据组数，每组测试数据描述如下:

第一行输入一个整数$n(1≤n≤10^9)$，表示$Plog$的点赞数。

输出描述

对于每组测试数据，新起一行，如果点赞数是好数，输出$YES$，否则输出$NO$。

样例1

输入

3
2
5 
12

输出

NO
YES
YES

说明

对于样例数据，$2$的本质不同质因子只有$2$，而$2$不是奇数，因此$2$不是好数