철사 잇기

큰 원의 둘레에 못 $N$개를 같은 간격으로 박았다. 그중 한 못을 $P_0$이라 하고, 거기서 시계 방향으로 나머지 못에 차례로 $P_1$부터 $P_{N-1}$까지 이름을 붙인다.

철사는 다음 규칙으로 잇는다.

1. $Q_0 = P_0$으로 둔다.
2. $p$단계를 $1$단계부터 $N^2$단계까지 반복한다. $Q_{p-1} = P_k$이면 $Q_p = P_{(k+p) \bmod N}$으로 정하고, $Q_{p-1}$과 $Q_p$를 철사로 잇는다. 두 못이 이미 이어져 있으면 새로 잇지 않는다. $Q_{p-1}$과 $Q_p$가 같은 못이면 잇지 않는다.

모든 단계를 마친 뒤 이어진 철사가 몇 개인지 구하라.

첫째 줄에 자연수 $N$이 주어진다. ($3 \le N \le 10^{12}$)

첫째 줄에 이어진 철사의 개수를 출력한다.