8859: [yosupo] Number Theory - Primitive Root
[Creator : ]
Description
Given $Q$ cases. For each case, given a prime $p$. Print a primitive root modulo $p$.
Input
$Q$
$p_0$
$p_1$
:
$p_{Q - 1}$
$p_0$
$p_1$
:
$p_{Q - 1}$
Output
Print $Q$ lines. For each line, print a primitive root $r$ ($0 \leq r < p$) of $p$.
Constraints
- $1 \leq Q \leq 100$
- $2 \leq p \leq 10^{18}$
- $p$ is a prime
- $2 \leq p \leq 10^{18}$
- $p$ is a prime
Sample 1 Input
8
2
3
5
7
11
13
17
19
Sample 1 Output
1
2
2
3
2
2
3
2
Sample 2 Input
3
998244353
1000000007
999999999999999989
Sample 2 Output
3
5
2