原根 (Primitive Root)

时间限制：10 秒

题目描述

给定 $Q$ 组数据。对于每组数据，给定一个质数 $p$。输出模 $p$ 的一个原根。

约束条件

• $1 \le Q \le 100$
• $2 \le p \le 10^{18}$
• $p$ 是质数

输入

Q
p_0
p_1
⋮
p_{Q-1}

输出

输出 $Q$ 行。对于每一行，输出 $p$ 的一个原根 $r$（$0 \le r < p$）。

8
2
3
5
7
11
13
17
19

1
2
2
3
2
2
3
2

3
998244353
1000000007
999999999999999989

3
5
2