Background

She is a grain of sand that sneaks in at midnight, drifting with the sea breeze.

The aurora makes a wish for tomorrow together with her.

She leaps up, and radio waves spread across the sky, yet the sea remains calm.

“May the world be full of blooming flowers.”

Problem Description

Given an integer $n$.

You need to compute $\bigoplus\limits_{i=1}^{n} \gcd(i,n)$, that is, the value of $\gcd(1,n) \oplus \gcd(2,n) \oplus \cdots \oplus \gcd(n,n)$. Here, $\gcd(a,b)$ denotes the greatest common divisor, and $\bigoplus$ denotes bitwise XOR, i.e. ^ in C++.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, which represents the number of test cases.

Then each test case follows. For each test case, one line contains one integer $n$.

Output Format

For each test case, output one line with one integer, representing the value of $\bigoplus\limits_{i=1}^{n} \gcd(i,n)$.

3
2
3
6

3
3
5

Hint

"Sample Explanation #1"

For the $1$st test case, $\bigoplus\limits_{i=1}^{2} \gcd(i,2)=\gcd(1,2)\oplus\gcd(2,2)=1\oplus2=3$.

For the $2$nd test case, $\bigoplus\limits_{i=1}^{3} \gcd(i,3)=\gcd(1,3)\oplus\gcd(2,3)\oplus\gcd(3,3)=1\oplus1\oplus3=3$.

"Constraints"

For all testdata, $1 \le T \le 100$, $1 \le n \le 10^{18}$.

You can only get the score for this problem if you pass all test points.

Translated by ChatGPT 5