P9913 "RiOI-03" water problem

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.

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

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

### 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