Problem Description:
If you know what is XOR and Binary Representation of number you can skip to problem statement.
What is a binary representation of a number ?

All computer calculations are done in binary system that is system containing only 0’s and 1’s. Number, character, images and everything is represented and stored on computer in this form only. For this problem we will just consider integers. Before computations all computers convert entered integers into binary representation related to that number and then perform operations on it.
So, how do we convert given integer into its binary representation ?
Lets try to understand this by an example.

Suppose you want to find binary representation of n = 10.
We will follow this procedure.

Divide n by 2, remainder we get after this operation is 0, let's name this remainder as R0.

After above division n will be 5.
Divide n by 2, remainder we get after this operation is 1, let's name this remainder as R1.

After above division n will be 2. (In computers 5/2 = 2, if 5 or 2 is not of type double or float).

Divide n by 2, remainder we get after this operation is 0, let's name this remainder as R2.

After above division n will be 1.

So, we will stop here. Let's name this 1 as R3.
Now, final binary representation of n = 10 will be R3R2R1R0 i.e 1010.

Lets take another example. Find binary representation for n=7

We will follow the same procedure as above.
Divide n by 2, remainder will be 1, name this remainder as R0.
Now, n will be 3.

Divide n by 2, remainder will be 1, name this remainder as R1.

Now, n will be 1.

Stop here, name this 1 as R2.

Now, final binary representation of n = 7 will be R2R1R0 i.e 111
Similarly by following the above procedure we can find the binary representation of each number. Don’t worry for this problem you don’t need to find the representation. Computer do this internally.
In binary representation each 0 or 1 is a separate bit.

Now, what is XOR ?

XOR is defined as exclusive or for two integers say a and b.
To find XOR, we will first find the binary representation of both a and b.

Lets do this also by example. Suppose a = 7 and b = 10.

So binary representation of a = 111 (see explanation above) and b = 1010 (see explanation above).

Now if we add 0 before integers it remains same, this applies to binary representation also. As binary representation of a contains less bits than b we will write a as 0111 because adding 0 before doesn’t make any difference.

Now XOR of a and b will be :
a = 0 1 1 1 (I have expressed the representation by spaces just for easy understanding)
b = 1 0 1 0
XOR= 1 1 0 1
i.e we find XOR for each corresponding bits.
First lets see the rules for XOR
Rule 1 : If both bits are 1 then XOR’ed bit will be 0.
Rule 2 : If both bits are 0 then XOR’ed bit will be 0.
Rule 3 : If one bit is 0 and one bit is 1 XOR’ed bit will be 1.

In the above example we find XOR’ed bit for each corresponding pair of bits.

(First Bit Pair) 0 XOR 1 = 1 (Rule 3)
(Second Bit Pair) 1 XOR 0 = 1 (Rule 3)
(Third Bit Pair) 1 XOR 1 = 0 (Rule 1)
(Fourth Bit Pair) 1 XOR 0 = 1 (Rule 3)

So, finally we get a XOR b as 1101.
To find XOR of more than two numbers, represent all numbers in binary representation, add 0’s before if necessary. Write them like this.

0 1 1 1 0
0 1 1 0 1
1 0 0 1 0

and so on.
To find each bit of XOR just calculate number of 1’s in the corresponding bits. If it is even or zero then that XOR’ed bit is 0. If it is odd then that XOR’ed bit is 1.
For the above example.

(First corresponding bits) 0 XOR 0 XOR 1 = 1
(Second corresponding bits) 1 XOR 1 XOR 0 = 0
(Third corresponding bits) 1 XOR 1 XOR 0 = 0
(Fourth corresponding bits) 1 XOR 0 XOR 1 = 0
(Fifth corresponding bits) 0 XOR 1 XOR 0 = 1

So, final XOR will be 10001.

So, this seems to be complicated. In all languages you can XOR two integers say a and b by ‘^’ this operation.
i.e to find a XOR b, just do a^b (this operation is defined in all languages).

Some more rules related to XOR (now i will just represent XOR by ‘^’).

a^a = 0
0^a = a

Problem Statement:
You will be given a number x. You have to find the value of XOR of [1, x] i.e 1^2^3^4………………..^x.

Input:

First line contains integer t denoting number of test cases.
Each test case contains one line containing special number x.

Output:
For each test case print the value of XOR of [1,x].

Constraints:
45 Points:
1<=t<=10
1<=x<=1000000

55 Points:
1<=t<=750000
1<=x<=10000000000

Example:

Sample Input:
2
1
3

Sample Output:
1
0

Sample Explanation:

For ‘1’ the answer is obviously 1.
For ‘3’, 1 XOR 2 XOR 3 is 0.

见题面

见题面