# 「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)$ 的值。

## 样例 #1

### 样例输入 #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}$。

**只有你通过本题的所有测试点，你才能获得本题的分数。**