In modular arithmetic, a number $g$ is a primitive root modulo $n$ if every number a coprime to $n$ is congruent to a power of $g$ modulo $n$. That is, $g$ is a primitive root modulo $n$ if for every integer $a$ coprime to $n$, there is some integer $k$ for which $g^k \equiv a \pmod n$.

Given an integer $n$, you need to find any primitive root modulo $n$, or claim that it doesn't exist.

Input

The first line of the input consists a single integer $n$ ($1 \le n \le 10^{16}$).

Output

If there's no primitive root modulo $n$, print -1.

Otherwise, print a single integer $g$, indicating your solution. If there are multiple possible solutions, you may print any of them.

Example

Input 1

2

Output 1

1

Input 2

17

Output 2

3

Input 3

20014

Output 3

5

Input 4

230000

Output 4

-1

Scoring

Let $p \ge 3$ be an odd prime number, and $k > 0$ be a positive integer.