Background

A check-in problem……

Problem Description

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.

Input Format

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.

Output Format

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

3
1
5
10

1
5
8

Hint

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.

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