{"raw_statement":[{"iden":"background","content":"她是午夜潜入海风漂流的沙砾\n\n极光与她一齐许下明日愿景\n\n飞身电波铺满天穹而海仍平静\n\n“愿世界都繁花似锦”"},{"iden":"statement","content":"给定一个整数 $n$。\n\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++ 中的 `^`。"},{"iden":"input","content":"**本题有多组测试数据。**\n\n第一行输入一个整数 $T$，表示测试数据组数。\n\n接下来依次输入每组测试数据。对于每组测试数据，输入一行一个整数 $n$。"},{"iden":"output","content":"对于每组测试数据，输出一行一个整数，表示 $\\bigoplus\\limits_{i=1}^{n} \\gcd(i,n)$ 的值。"},{"iden":"note","content":"#### 「样例解释 #1」\n\n对于第 $1$ 组数据，$\\bigoplus\\limits_{i=1}^{2} \\gcd(i,2)=\\gcd(1,2)\\oplus\\gcd(2,2)=1\\oplus2=3$。\n\n对于第 $2$ 组数据，$\\bigoplus\\limits_{i=1}^{3} \\gcd(i,3)=\\gcd(1,3)\\oplus\\gcd(2,3)\\oplus\\gcd(3,3)=1\\oplus1\\oplus3=3$。\n\n#### 「数据范围」\n\n对于所有数据，$1 \\le T \\le 100$，$1 \\le n \\le 10^{18}$。\n\n**只有你通过本题的所有测试点，你才能获得本题的分数。**"}],"translated_statement":null,"sample_group":[["3\n2\n3\n6\n","3\n3\n5"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}