We all know the Fermat's Little Theorem:

A^(P - 1) % P = 1 (P is a prime number)

Curious pyy wanted to know the smallest A that satisfies the above equation with the given P

However, he found that 1 is the answer every time!

Therefore, we also require A to meet another equation:

A^j % P ≠ 1 (Mod P) j∈[1,P-2]

We have multiply cases. For each case:

The only one line contains a integer P(2 <= P <= 6000) (P is a prime number)

For each case, the minimal A should be output.

3

2