Description

There are now $n$ people, and lhm has a cake of mass $1$. Everyone wants to eat lhm’s cake. To maintain fairness and justice, lhm needs to use the minimum number of cuts to divide the cake into $n$ equal shares (one share may contain multiple pieces).

Treat the cake as a circle. Note that each time you cut the cake, you can only cut along a diameter.

In the end, the number of pieces each person gets may be different, but you must ensure that each person receives mass $\frac{1}{n}$.

You need to find the minimum number of cuts lhm needs to make.

Input Format

This problem contains multiple test cases.

The input has $t+1$ lines.

The first line contains an integer $t$, representing the number of test cases.

The next $t$ lines each contain an integer $n$, representing the number of people.

Output Format

Output $t$ lines. Each line contains a positive integer, representing the answer.

2
2
3

1
2

Hint

[Sample Explanation]

When $n=2$, we cut directly along a diameter, obtaining two cake pieces each of mass $\frac{1}{2}$. Give them to the two people.

When $n=3$, we can cut along two diameters with an angle of $60 \degree$ between them, obtaining two pieces $a,b$ of mass $\frac{1}{6}$ and two pieces $c,d$ of mass $\frac{1}{3}$. We give $a,b$ to the first person, and give $c,d$ to the second and third person respectively, achieving fairness and justice.

[Constraints]

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

For another $20\%$ of the testdata, $t=1$.

For $100\%$ of the testdata, $1 \le t \le 10^3$, $1 \le n \le 10^{9}$.

Translated by ChatGPT 5