B. Xor Sums
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Diego knows that the sum of all integers between $$$1$$$ and $$$N$$$ is $$$\frac{N(N+1)}{2}$$$. However, he is wondering how to compute the exclusive or of all integers between $$$1$$$ and $$$N$$$.

Exclusive or is also known as xor. Most programming languages represent it with the character ^.

Input

First, a single integer, $$$T$$$ $$$(1 \le T \le 10^5)$$$: the number of test cases.

Then $$$T$$$ lines, each of which contains a single integer, $$$N$$$ $$$(1 \le N \le 10^{18})$$$.

Output

For each test case output a line containing a single integer: the exclusive or of every number between $$$1$$$ and $$$N$$$.

Example
Input
3
1
2
5
Output
1
3
1