题目描述

给定一个整数 $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}$。

只有你通过本题的所有测试点，你才能获得本题的分数。