P9451 [ZSHOI-R1] New Concept Counting

What background does Div.2 A need?

Now Xttttr and his npy are playing a counting game, but they really like the number $2$, so they made the following rules: - If a number $a$ satisfies $\operatorname{popcount}(a) \geq 3$, then this number is illegal, and the other person must answer ``No,Commander``. - Otherwise, this number is legal, and the other person must answer the next legal number. As someone sitting nearby, you of course do not know the fun of this game. You only want to know what the other person should answer after a certain count.

The first line contains a positive integer $T$, which indicates the number of queries. The next $T$ lines each contain a natural number $a$, which indicates the number called out by one person in this query.

Output $T$ lines. Each line contains a positive integer or a string, indicating what the other person should answer for this query.

For $20\%$ of the testdata, $T \leq 100$ and $a \leq 10^4$. For another $20\%$ of the testdata, $a$ is a legal number. For another $20\%$ of the testdata, $a$ is uniformly random within the value range. For $100\%$ of the testdata, $1 \leq T \leq 10^5$ and $0 \leq a < 2^{63}$. Translated by ChatGPT 5