問題文

整数 $p$ が与えられます。正整数 $e$ であって、 $p$ と互いに素なあらゆる正整数 $q$ に対して

が成り立つような最小のものを答えてください。

制約

• $2 \le p \le 10^9$
• $p$ は整数である。

入力

出力

答えを $1$ 行に出力せよ。

入出力例

7

6

19

18

65537

65536