T419838 「YAC Round 2」八云蓝的 gcd 问题

 > 橙 ~~~~~~~ ！

八云蓝号称是幻想乡的数字的魔术师、最强式神、拥有验证哥德巴赫猜想程度的能力、拥有超越深蓝计算机程度的能力（笑）。最近她感到无聊，毕竟三途河的宽度、~~八云紫的年龄~~ 也都已经算出来了，于是想了一个有关 $\text{gcd}$ （最大公约数）的问题，来考验一下幻想乡其他人（人类？妖精？妖怪？月人？......）的智商。~~智商 9999999 琪露诺请求出战！！！~~ 问题很简单，描述如下： 给定一个整数 $n$。你需要求出 $\bigoplus _{i=1}^{n} \gcd(i,n)$ ，即 $\gcd(1,n) \oplus \gcd(2,n) \oplus \cdots \oplus \gcd(n,n)$ 的值。 其中 $\gcd(a,b)$ 就是 $a$ 和 $b$ 的最大公约数，$\oplus$ 表示 **按位异或** 运算。

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

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

#### 数据范围 对于前 $20 \%$ 的数据，$1 \le T \le 100$，$1 \le n \le 10^{5}$ ； 对于前 $100 \%$ 数据，$1 \le T \le 10^5$，$1 \le n \le 10^{18}$。