Primitive Root

Problem Description

Answer $T$ queries; each query gives a prime $p$, and you must output its smallest primitive root $g$.

Input Format

The first line contains an integer $T$. The following $T$ lines each contain one integer $p$.

Output Format

Output one integer: the smallest primitive root.

Sample Input

3
2
178187
998244353

Sample Output

1
2
3

Constraints

For all data, $T \leq 100$, $2 \leq p \leq 10^9$, and $p$ is prime.