Pass the Number

There is a team of \(n\) people numbered from 1 to \(n\). Starting from the first person, a number is passed sequentially from one person to the next until it reaches the \(n\)th person. The rules for transmitting the number are as follows:

• The first person starts with the number \(1\).
• If the current person has an odd index \(i\), then they pass the number to the next person using the bitwise AND operation with the next person’s index, i.e. the next number becomes \(current \; \& \; (i+1)\).
• If the current person has an even index \(i\), then they pass the number to the next person using the bitwise XOR operation with the next person’s index, i.e. the next number becomes \(current \; \oplus \; (i+1)\).

Your task is to compute the final number received by the \(n\)th person. There will be \(t\) test cases.

inputFormat

The input begins with an integer \(t\) (the number of test cases). Each test case consists of a single integer \(n\), which represents the number of people in the team.

Constraints:

• \(1 \leq t \leq 10^5\)
• \(1 \leq n \leq 10^9\)

outputFormat

For each test case, output a single line containing the final number received by the \(n\)th person.

sample

3
1
2
3

1
0
3