#1486. 「Cfz Round 3」Xor with Gcd

「Cfz Round 3」Xor with Gcd

题目描述

给定一个整数 nn。

你需要求出 ⨁i=1ngcd⁡(i,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)\gcd(a,b) 表示 aa 和 bb 的最大公约数,⨁\bigoplus 表示按位异或,即 C++ 中的 ^。

输入格式

本题有多组测试数据。

第一行输入一个整数 TT,表示测试数据组数。

接下来依次输入每组测试数据。对于每组测试数据,输入一行一个整数 nn。

输出格式

对于每组测试数据,输出一行一个整数,表示 ⨁i=1ngcd⁡(i,n)\bigoplus\limits_{i=1}^{n} \gcd(i,n) 的值。

样例

3
2
3
6
3
3
5

题目来源:洛谷 P10031