P7573 "PMOI-3" Fairness and Justice

> Fairness and justice require sacrifice. — *Detective Chinatown 3*.

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.

**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 $t$ lines. Each line contains a positive integer, representing the answer.

[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