Background

She is the grit drifting in the sea breeze at midnight, The aurora and she make a wish for tomorrow together. Leaping into the radio waves that fill the sky while the sea remains calm, "May the world be filled with blooming flowers."

Description

Given an integer $n$.

You need to calculate the value of $\bigoplus\limits_{i=1}^{n} \gcd(i,n)$, which is $\gcd(1,n) \oplus \gcd(2,n) \oplus \cdots \oplus \gcd(n,n)$. Here, $\gcd(a,b)$ denotes the greatest common divisor of $a$ and $b$, and $\bigoplus$ denotes the bitwise XOR operation, which is ^ in C++.

Input

This problem contains multiple test cases.

The first line contains an integer $T$, representing the number of test cases.

Each test case follows. For each test case, input a single line containing an integer $n$.

Output

For each test case, output a single line containing an integer representing the value of $\bigoplus\limits_{i=1}^{n} \gcd(i,n)$.

Examples

Input 1

3
2
3
6

Output 1

3
3
5

Note 1

For the first test case, $\bigoplus\limits_{i=1}^{2} \gcd(i,2)=\gcd(1,2)\oplus\gcd(2,2)=1\oplus2=3$.

For the second test case, $\bigoplus\limits_{i=1}^{3} \gcd(i,3)=\gcd(1,3)\oplus\gcd(2,3)\oplus\gcd(3,3)=1\oplus1\oplus3=3$.

Constraints

For all test cases, $1 \le T \le 100$, $1 \le n \le 10^{18}$.