I - 1<->k Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : {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 です。

原案 : turtle0123__