310526: CF1846E2. Rudolf and Snowflakes (hard version)

E2. Rudolf and Snowflakes (hard version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is the hard version of the problem. The only difference is that in this version $n \le 10^{18}$.

One winter morning, Rudolf was looking thoughtfully out the window, watching the falling snowflakes. He quickly noticed a certain symmetry in the configuration of the snowflakes. And like a true mathematician, Rudolf came up with a mathematical model of a snowflake.

He defined a snowflake as an undirected graph constructed according to the following rules:

• Initially, the graph has only one vertex.
• Then, more vertices are added to the graph. The initial vertex is connected by edges to $k$ new vertices ($k > 1$).
• Each vertex that is connected to only one other vertex is connected by edges to $k$ more new vertices. This step should be done at least once.

The smallest possible snowflake for $k = 4$ is shown in the figure.

After some mathematical research, Rudolf realized that such snowflakes may not have any number of vertices. Help Rudolf check whether a snowflake with $n$ vertices can exist.

Input

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Then follow the descriptions of the test cases.

The first line of each test case contains an integer $n$ ($1 \le n \le 10^{18}$) — the number of vertices for which it is necessary to check the existence of a snowflake.

Output

Output $t$ lines, each of which is the answer to the corresponding test case — "YES" if there exists such $k > 1$ that a snowflake with the given number of vertices can be constructed; "NO" otherwise.

ExampleInput

9
1
2
3
6
13
15
255
10101
1000000000000000000

Output

NO
NO
NO
NO
YES
YES
YES
YES
NO

题目大意：
这个问题是“Rudolf和雪花”难题的困难版本。在这个版本中，唯一的区别是n≤10^18。一个冬天的早晨，Rudolf在窗前若有所思地观察着飘落的雪花，他很快注意到雪花配置中存在一定的对称性。作为一个真正的数学家，Rudolf提出了一个雪花的数学模型。他将雪花定义为一个根据以下规则构建的无向图：最初，图只有一个顶点。然后，图的初始顶点通过边连接到k个新顶点（k>1）。每个只连接一个其他顶点的顶点通过边连接到k个新顶点。这一步至少要做一次。对于k=4，最小的可能的雪花如图所示。经过一些数学研究，Rudolf意识到这样的雪花可能不存在任何数量的顶点。帮助Rudolf检查是否存在具有n个顶点的雪花。

输入输出数据格式：
输入：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
然后是测试用例的描述。
每个测试用例的第一行包含一个整数n（1≤n≤10^18）——需要检查雪花存在性的顶点数。

输出：
输出t行，每行是对应测试用例的答案——如果存在这样的k>1，使得可以构建具有给定顶点数的雪花，则输出“YES”；否则输出“NO”。题目大意： 这个问题是“Rudolf和雪花”难题的困难版本。在这个版本中，唯一的区别是n≤10^18。一个冬天的早晨，Rudolf在窗前若有所思地观察着飘落的雪花，他很快注意到雪花配置中存在一定的对称性。作为一个真正的数学家，Rudolf提出了一个雪花的数学模型。他将雪花定义为一个根据以下规则构建的无向图：最初，图只有一个顶点。然后，图的初始顶点通过边连接到k个新顶点（k>1）。每个只连接一个其他顶点的顶点通过边连接到k个新顶点。这一步至少要做一次。对于k=4，最小的可能的雪花如图所示。经过一些数学研究，Rudolf意识到这样的雪花可能不存在任何数量的顶点。帮助Rudolf检查是否存在具有n个顶点的雪花。 输入输出数据格式： 输入： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 然后是测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤10^18）——需要检查雪花存在性的顶点数。 输出： 输出t行，每行是对应测试用例的答案——如果存在这样的k>1，使得可以构建具有给定顶点数的雪花，则输出“YES”；否则输出“NO”。