题目背景

她是午夜潜入海风漂流的沙砾

极光与她一齐许下明日愿景

飞身电波铺满天穹而海仍平静

“愿世界都繁花似锦”

题目描述

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

样例 1 输入

3
2
3
6

样例 1 输出

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}$。