정다각형의 최소 정다각형 꼭짓점

시간 제한2초메모리 제한512 MB

요약

정N각형이 주어질 때, 그 꼭짓점 일부를 골라 만들 수 있는 정다각형 중 꼭짓점 수가 가장 작은 것을 구한다.

문제

정 $N$ 각형이 주어진다. 이 꼭짓점 중 일부를 골라 정다각형을 이루려고 할 때, 고를 수 있는 꼭짓점의 수의 최솟값을 구하여라.

입력은 정수 $N$ 하나로 이루어진다. ( $3 \le N \le 10^{12}$ )

주어진 다각형의 꼭짓점 중 정다각형을 이루는 것들의 최소 개수를 출력한다.