시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 24 10 10 43.478%

문제

상근이와 정인이는 숫자 맞추기 게임을 하고 있다.

먼저, 정인이는 1보다 크거나 같고, n보다 작거나 같은 자연수 하나를 생각한다.

상근이는 정인이에게 생각한 숫자가 x인지 물어볼 수 있다. 이 때 정인이는 자신이 생각한 숫자와 x의 최대공약수가 몇 인지 말해준다.

다음은 n=6일 때 가능한 상근이와 정인이의 대화이다.

상근: 3이야?

정인: 3이랑 내가 생각한 숫자의 최대공약수는 1이야.

상근: (음... 그럼 3이랑 6은 아니네? 근데 1,2,4,5는 될 수 있어!) 그럼 2야?

정인: 2랑 내가 생각한 숫자의 최대공약수는 2야.

상근: (오!? 그럼 1, 5는 아니겠네?) 너가 생각한 숫자는 4야 맞지?

정인: 4랑 내가 생각한 숫자의 최대공약수는 2야.

상근: 그럼 니가 생각한 숫자는 2네 ㅋㅋㅋ

위의 예에서 상근이는 정인이가 생각한 숫자를 맞추기 위해서 질문을 총 3번 했다. 하지만, n=6인 경우에 항상 2번의 질문으로 정인이가 생각한 숫자를 맞출 수 있다.

제일 먼저 상근이는 6을 물어보면 된다. 만약 정인이가 1이라고 대답했다면, 정인이가 생각한 숫자는 1과 5중 하나이기 때문에, 2번 질문으로 맞출 수 있다. 정인이의 대답이 2라면, 정인이가 생각한 숫자는 2와 4중 하나이다. 만약, 정인이가 3이라고 대답했다면, 정답은 3이고, 6이라고 대답했다면 6이다.

따라서, 상근이는 최대 2번의 질문으로 정인이가 생각한 숫자를 맞출 수 있다.

n이 주어졌을 때, 상근이가 최적의 방법으로 질문했을 때, 최대 몇 번 만에 정인이가 생각한 숫자를 맞출 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. 2 ≤ n ≤ 10,000

출력

첫째 줄에 상근이가 최적의 방법으로 질문했을 때, 최대 몇 번의 질문으로 정인이가 생각한 숫자를 맞출 수 있는지 출력한다.

예제 입력

6

예제 출력

2

힌트