There is a special array created by Barbarian for his beautiful Arrayland where $A_1$ is $1$ always.

Each $A_i$ is generated as:

$A_i = (A_1 \; \oplus \; A_2 \; \oplus \; A_3 .......... A_{i-2} \; \oplus \; A_{i-1} \; \oplus \; i) (\oplus \; is \; XOR)$  $\forall i>1$.

Input:

The first line contains an integer $T$ denoting the number of test cases. Next  line contains $T$  integers $N$, denoting the index of the array for which you need to print the answer.

Output:

Print $A_n$ corresponding to the  N in a separate line for each test case.

Constraint:
$T=100000 \\ 1 \le N \le 10^6$