Rudolf and Snowflakes (hard version)
Contest: Codeforces Round 883 (Div. 3)
Difficulty rating: 1800
Tags: binary search, brute force, implementation, math

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
9
1
2
3
6
13
15
255
10101
1000000000000000000

Example output:
NO
NO
NO
NO
YES
YES
YES
YES
NO

Editorial:
On these constraints, it is also possible to precalculate whether it is possible to obtain certain values of $$$n$$$ for some $$$k$$$. To do this, we can iterate through all possible $$$2 \le k \le 10^6$$$ and for each of them calculate the values $$$1 + k + k^2$$$, $$$1 + k + k^2 + k^3$$$, ..., $$$1 + k + k^2 + k^3 + ... + k^p$$$, where $$$p$$$ is such that $$$1 \le 1 + k + k^2 + k^3 + ... + k^p \le 10^{18}$$$. However, in order to obtain all possible values of $$$n$$$, we would have to iterate through $$$k \le 10^9$$$, which exceeds the time limits. Therefore, let's precalculate all possible values of $$$n$$$ that can be obtained for $$$3 \le p \le 63$$$.
We will store all the obtained values, for example, in a set. We cannot use an array called "used" here due to the constraints on $$$n$$$.
It is better to perform this precalculation before iterating through the test cases of the current test case.
Next, for each test, we only need to read the value of $$$n$$$ and check if we obtained it in the aforementioned precalculation.
If we obtained it, we output "YES" and move on to the next test.
If we did not obtain it, we need to separately check if we could obtain this value for $$$p = 2$$$. To do this, we solve the quadratic equation $$$k^2 + k + 1 = n$$$. If it has integer roots that satisfy the problem's constraints ($$$k > 1$$$), then the answer is "YES". Otherwise, it is "NO".
The time complexity of the solution is $$$O(\sqrt[3] n \cdot p \cdot \log n + tc \cdot \log n)$$$.
Here, $$$tc$$$ is the number of tests in the test case.