#P1846E2. Rudolf and Snowflakes (hard version)

    ID: 8865 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>binary searchbrute forceimplementationmath

Rudolf and Snowflakes (hard version)

Description

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.

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 $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.

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.

9
1
2
3
6
13
15
255
10101
1000000000000000000
NO
NO
NO
NO
YES
YES
YES
YES
NO