항등 함수

정수 $N$이 주어진다. $N$은 $1$보다 크다.

다음 함수를 생각하자.

• $f(a) = a^N \bmod N$
• $F_1(a) = f(a)$
• $F_{k+1}(a) = F_k(f(a))$ ($k = 1,2,3,\ldots$)

$\mathrm{mod}$는 정수의 나머지 연산을 나타낸다. 음이 아닌 정수 $x$와 양의 정수 $y$에 대해, $x \bmod y$는 $x$를 $y$로 나눈 나머지이다.

$N$보다 작은 모든 양의 정수 $a$에 대해 $F_k(a) = a$가 성립하는 최소 양의 정수 $k$를 출력하라. 그러한 $k$가 존재하지 않으면 $-1$을 출력하라.

입력은 한 줄이며, 정수 $N$ ($2 \le N \le 10^9$)이 주어진다. $N$의 의미는 문제 본문에 설명되어 있다.

$N$보다 작은 모든 양의 정수 $a$에 대해 $F_k(a) = a$가 성립하는 최소 양의 정수 $k$를 출력하라. 그러한 $k$가 존재하지 않으면 $-1$을 출력하라.