E1. Rudolf and Snowflakes (simple version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis is a simple version of the problem. The only difference is that in this version n \le 10^6.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 if a snowflake with n vertices can exist.InputThe 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^6) — the number of vertices for which it is necessary to check the existence of a snowflake.OutputOutput t lines, each of which is the answer to the corresponding test case — "YES" if there exists such k > 1 for which a snowflake with the given number of vertices can be constructed; "NO" otherwise.ExampleInput
912361315255101011000000Output
NO
NO
NO
NO
YES
YES
YES
YES
NO

912361315255101011000000
NO NO NO NO YES YES YES YES NO 
['brute force', 'implementation', 'math', '*1300']