这是问题的简单版本。唯一的区别是在这个版本中 $$$n \le 10^6$$$。
一个冬天的早晨,鲁道夫若有所思地看着窗外,看着飘落的雪花。他很快注意到雪花的形状具有一定的对称性。就像一位真正的数学家一样,鲁道夫提出了雪花的数学模型。
他将雪花定义为根据以下规则构造的无向图:
- 最初,该图只有一个顶点。
- 然后,更多顶点被添加到图中。初始顶点通过边连接到 $$$k$$$ 个新顶点 ($$$k > 1$$$)。
- 每个仅连接到另一个顶点的顶点通过边连接到 $$$k$$$ 个新顶点。此步骤应至少执行一次。
图中显示了 $$$k = 4$$$ 的最小可能雪花。
经过一些数学研究,鲁道夫意识到这样的雪花可能没有任何数量的顶点。帮助鲁道夫检查是否存在具有 $$$n$$$ 顶点的雪花。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
然后按照测试用例的描述进行操作。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 需要检查雪花是否存在的顶点数。
输出
输出 $$$t$$$ 行,每行都是相应测试用例的答案 - 如果存在这样的 $$$k > 1$$$ 可以构造具有给定顶点数的雪花,则为“YES”;否则“不”。
示例
输入 #1
9 1 2 3 6 13 15 255 10101 1000000
输出 #1
NO NO NO NO YES YES YES YES NO