(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

View problem - Wiring (kriii2_W)

Time limitMemory limit# of submissions# of submitted usersSolved #Accepted user ratio
1000 ms256 MiB703434100.00%

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

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

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

입력 형식

첫 번째 줄에 자연수 $N$이 주어진다.

쉬운 문제에서는 $3 \le N \le 1,000$인 입력이 주어진다.

어려운 문제에서는 $3 \le N \le 10^{12}$인 입력이 주어진다.

출력 형식

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

예제 1

입력

3

출력

1

예제 2

입력

4

출력

3

예제 3

입력

5

출력

2