QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 10 Hackable ✓
Statistics

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.

Test Set $m$ Constraints
$1$ $\le 1\,000$ $m = p$
$2$ $m = p^k$
$3$ None
$4$ $\le 10^6$ $m = p$
$5$ $m = p^k$
$6$ None
$7$ $\le 10^9$ $m = p$
$8$ $m = p^k$
$9$ None
$10$ $\le 10^{16}$

在模算数中,整数 $g$ 被称为模 $n$ 意义下的原根,当且仅当所有与 $n$ 互素的数都在模 $n$ 的意义下对应了 $g$ 的幂。即,$g$ 是模 $n$ 意义下的原根,当且仅当对所有满足与 $n$ 互素的整数 $a$,都存在一个非负整数 $k$,使得 $a \equiv g^k \pmod n$。

给定一个整数 $n$,你需要找到任意一个模 $n$ 意义下的原根 ,或说明它不存在。

Input

输入的第一行包含一个整数 $n$ ($1 \le n \le 10^{16}$)。

Output

如果不存在模 $n$ 意义下的原根,输出 -1

否则,输出一个整数 $g$,表示你找到的解。如果存在多种可能的解,你可以输出任意一个。

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

设 $p \ge 3$ 为任意奇素数,$k > 0$ 为任意正整数。

测试包 $m$ 额外限制
$1$ $\le 1\,000$ $m = p$
$2$ $m = p^k$
$3$
$4$ $\le 10^6$ $m = p$
$5$ $m = p^k$
$6$
$7$ $\le 10^9$ $m = p$
$8$ $m = p^k$
$9$
$10$ $\le 10^{16}$