← 返回题目列表

Codeforces · 1846/E1

E1. 鲁道夫和雪花(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。唯一的区别是在这个版本中 $$$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