P10405 "SMOI-R1" Queue

A check-in problem……

There is a queue with $n$ people. The $i$-th person in the queue has ID $i$. Starting from the first person, a number is passed to the next person one by one, until it reaches person $n$. The rule for passing the number to the next person is: - The first person's number is $1$. - If this person's ID is odd, then the number passed to the next person is the current number **bitwise AND** with the next person's ID. - If this person's ID is even, then the number passed to the next person is the current number **bitwise XOR** with the next person's ID. Find the number passed to person $n$. But computing just one case is too easy, so you need to handle $t$ cases.

**This problem has multiple test cases**. The first line contains an integer $t$, the number of test cases. For each test case: There is only one number $n$, representing the number of people in the queue.

For each test case, output one number, which is the number passed to person $n$.

### Sample Explanation For the second test case: - The number passed from the first person to the next is $1\operatorname{and}2=0$. - The number passed from the second person to the next is $0\operatorname{xor}3=3$. - The number passed from the third person to the next is $3\operatorname{and}4=0$. - The number passed from the fourth person to the next is $0\operatorname{xor}5=5$. So the answer is $5$. ### Constraints **This problem uses bundled testdata**. subtask ID|$t\leq$| $n\leq$| Score -|-|-|- $1$|$10^2$|$10^5$|$20$ $2$|$10^6$|$10^7$|$20$ $3$|$10^6$|$10^{18}$|$60$ For $100\%$ of the testdata, it is guaranteed that $1\le t\le10^6$ and $1\le n\le 10^{18}$。 Translated by ChatGPT 5