Problem Description

Given a positive integer $n$, determine whether a square can be divided into $n$ smaller squares (not necessarily of the same size). Output Yes or No. There are multiple test cases.

A non-strict definition of “dividing” can be understood as making one cut. However, each cut must be a line segment, and its endpoints must lie on the boundary of the square or on previously made cut segments.

Input Format

The first line contains a positive integer $T$.

For each test case, one line contains a positive integer $n$.

Output Format

For each test case, output one string per line: Yes or No, indicating whether such a division exists.

3
4
3
256

Yes
No
Yes

Hint

Sample Explanation 1

Clearly, a square cannot be divided into $3$ smaller squares.
Since $4 = 2^2$ and $256 = 16^2$, both of them can be divided into several congruent smaller squares.

Constraints

• Subtask 0 (10 pts): $n$ is even.
• Subtask 1 (35 pts): $n \leq 8$.
• Subtask 2 (55 pts): No special restrictions.

For all testdata, $1 \leq T \leq 10^5$ and $1 \leq n \leq 10^9$.

Translated by ChatGPT 5