在模算数中，整数 $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$ 为任意正整数。