10915번 - Wiring

형석이는 너무 심심했기 때문에 큰 원 위에 일정한 간격으로 N개의 못을 박았다. 그리고 어느 한 못을 P₀라고 하고, 이 못에서부터 시계방향으로 다른 못들을 P₁에서 P_N-1이라고 이름 붙였다. 그리고 이 못들을 철사로 연결하는 놀이를 시작했다. 얼마간 이 놀이를 반복하던 형석이는 그렸던 철사들을 모두 없애고 다음과 같이 철사를 연결하기로 했다.

1. Q₀ = P₀이라고 하자. 그리고 다음을 1단계에서부터 N²단계까지 반복한다.
2. p 단계에서는 Q_p-1 = P_k이면, Q_p = P_{(k+p) mod n}으로 하여, Q_p-1에서 Q_p까지를 철사로 연결한다. 만약 이미 두 못 이미 연결되어 있다면 연결하지 않는다. 또한, Q_p-1과 Q_p가 같은 못이라면 연결하지 않는 것으로 취급한다.

형석이가 연결하게 될 철사의 개수는 몇 개가 될 것인지 구해주자.

첫 번째 줄에 자연수 N이 주어진다. (3 ≤ N ≤ 10¹²)

첫 번째 줄에 형석이가 연결하게 될 철사의 개수를 출력한다.