原根

【题目描述】

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

【输入】

$Q$
$p_0$
$p_1$
:
$p_{Q - 1}$

【输出】

输出 $Q$ 行。每行输出 $p$ 的一个原根 $r$（$0 \leq r < p$）。

【输入样例】

8
2
3
5
7
11
13
17
19

【输出样例】

1
2
2
3
2
2
3
2

【输入样例2】

3
998244353
1000000007
999999999999999989

【输出样例2】

3
5
2

【数据范围】

• $1 \leq Q \leq 100$
• $2 \leq p \leq 1000000000000000000$
• $p$ 是质数

【来源】

Library Checker（yosupo06） primitive_root

本题为 special judge（输出任意合法解），暂不可本地评测。