406430: GYM102409 B Xor Sums

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 ^.

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})$$$.

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

3
1
2
5

1
3
1