시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 23 2 2 16.667%

문제

세준이는 동그랗게 생긴 사탕 통을 가지고 있다. 그 사탕 통에는 N개의 칸이 있는데, 원형으로 동그랗게 자리잡고 있다. 각 칸은 1번부터 N번까지 시계방향으로 번호 매겨져 있다.

처음에 세준이는 사탕을 아무 칸에나 넣을 수 있다. 그 후에는 사탕 통의 번호의 각 자리의 합만큼 시계방향으로 이동한다. 계속해서 위와같이 이동하다가 이전에 방문한 칸이 나오면 멈춘다.

사탕통의 크기가 주어지면, 최대 몇 개의 칸을 방문 할 수 있는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 200,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 방문할 수 있는 최대 칸의 개수를 출력한다.

예제 입력

4

예제 출력

3

힌트

출처