「Cfz Round 3」Xor with Gcd

她是午夜潜入海风漂流的沙砾 极光与她一齐许下明日愿景 飞身电波铺满天穹而海仍平静 “愿世界都繁花似锦”

给定一个整数 $n$。 你需要求出 $\bigoplus\limits_{i=1}^{n} \gcd(i,n)$，即 $\gcd(1,n) \oplus \gcd(2,n) \oplus \cdots \oplus \gcd(n,n)$ 的值。其中 $\gcd(a,b)$ 表示 $a$ 和 $b$ 的**最大公约数**，$\bigoplus$ 表示**按位异或**，即 C++ 中的 `^`。

**本题有多组测试数据。** 第一行输入一个整数 $T$，表示测试数据组数。 接下来依次输入每组测试数据。对于每组测试数据，输入一行一个整数 $n$。

对于每组测试数据，输出一行一个整数，表示 $\bigoplus\limits_{i=1}^{n} \gcd(i,n)$ 的值。

3
2
3
6

3
3
5

#### 「样例解释 #1」 对于第 $1$ 组数据，$\bigoplus\limits_{i=1}^{2} \gcd(i,2)=\gcd(1,2)\oplus\gcd(2,2)=1\oplus2=3$。 对于第 $2$ 组数据，$\bigoplus\limits_{i=1}^{3} \gcd(i,3)=\gcd(1,3)\oplus\gcd(2,3)\oplus\gcd(3,3)=1\oplus1\oplus3=3$。 #### 「数据范围」 对于所有数据，$1 \le T \le 100$，$1 \le n \le 10^{18}$。 **只有你通过本题的所有测试点，你才能获得本题的分数。**