← 返回题目列表

AtCoder · tkppc6_1_i

I. 1与k互换

中文机器翻译题面 查看原题

配点 : {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__