配点 : {500} 点
問題文
正整数 N 。 对于 0 \le k < N 的整数 选择 k , 选择最大化 k^2 \equiv 1 \pmod N 的项目数。
1 每个输入 给定 T 案例,找到每个案例的答案。
制約
- 所有输入均为整数
- 1 \le T \le 1000
- 2 \le N \le 10^9
入力
输入是按以下格式从标准输入给出的。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个案例均按以下格式给出。 打印
N
出力
T 行。 i 在线 \mathrm{case}_i 的答案。
入力例 1
3 3 14 1592
出力例 1
2 2 8
1^2 \equiv 1 \pmod 3, 2^2 \equiv 1 \pmod 3 。
原案 : 海龟0123__