Background

AzureHair was defeated by “Meow Meow” in NOIP 2022, and then got an incurable illness—fear of T2. So in NOIP 2023, he firmly skipped T2 and then spent two hours stuck on T3 with no result, leaving regretfully. His classmates decided to help him cure this incurable illness.

After his classmates cured his fear of T2, he confidently started his SDOI. Then he spent $2$ hours writing a partial solution but still could not finish, and left regretfully again.

Problem Description

AzureHair’s classmates lock AzureHair and $n$ cats in a room, and require that every day AzureHair hands over $\frac{n}{2}$ cats. But if $n$ is odd, AzureHair will struggle with whether to hand over $\frac{n+1}{2}$ cats or $\frac{n-1}{2}$ cats. AzureHair does not want to struggle, so please compute the minimum number of times he must struggle until all cats are taken out of the room.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$.

The next $T$ lines each contain one integer $n$.

Output Format

Output $T$ lines, each containing one integer representing the minimum number of times he struggles.

2
13
7

3
2

Hint

Sample Explanation

For $13$ cats, one process with only $3$ struggles is as follows:

Choose to hand over $7$ cats, leaving $6$;

No struggle, hand over $3$ cats, leaving $3$;

Choose to hand over $2$ cats, leaving $1$;

Choose to hand over $1$ cat, and all cats are taken away.

It is easy to prove that there is no plan with fewer than $3$ struggles.

Constraints

For $10\%$ of the testdata, $1 \le n \le 10$.

For $30\%$ of the testdata, $1 \le n \le 10^{5}$.

For $100\%$ of the testdata, $1 \le n \le 2^{60}$, $1 \le T \le 5 \times 10^5$.

Translated by ChatGPT 5