최대공약수 맞히기 게임

상근이와 정인이가 숫자 맞히기 게임을 한다.

먼저 정인이는 1 이상 n 이하의 자연수 하나를 마음속으로 정한다.

상근이는 1 이상 n 이하의 자연수 x를 골라 "네가 정한 수가 x야?"라고 물을 수 있다. 그러면 정인이는 자신이 정한 수와 x의 최대공약수를 알려 준다.

다음은 n = 6일 때 나눌 수 있는 대화의 한 예이다.

• 상근: 3이야?
• 정인: 3과 내가 정한 수의 최대공약수는 1이야.
• 상근: (그러면 3도 6도 아니고, 1·2·4·5 중 하나구나.) 그럼 2야?
• 정인: 2와 내가 정한 수의 최대공약수는 2야.
• 상근: (그러면 1도 5도 아니겠네.) 네가 정한 수는 4 맞지?
• 정인: 4와 내가 정한 수의 최대공약수는 2야.
• 상근: 아하, 그러면 네가 정한 수는 2구나.

이 예에서 상근이는 세 번 질문했지만, n = 6이라면 항상 두 번의 질문만으로 정인이의 수를 알아낼 수 있다.

먼저 6을 물어보면 된다. 대답이 1이면 정인이의 수는 1 또는 5이므로 한 번 더 물어 가려낼 수 있고, 대답이 2이면 2 또는 4이므로 마찬가지다. 대답이 3이면 답은 3이고, 대답이 6이면 답은 6이다. 따라서 두 번의 질문이면 충분하다.

n이 주어졌을 때, 상근이가 최적으로 질문한다면 최악의 경우에도 몇 번의 질문 안에 정인이가 정한 수를 반드시 알아낼 수 있는지 구하여라.

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

상근이가 최적으로 질문할 때, 최악의 경우 필요한 질문 횟수의 최댓값을 첫째 줄에 출력한다.