The GCD Guessing Game

Sanggeun and Jeongin are playing a number-guessing game.

First, Jeongin secretly picks one natural number between 1 and n, inclusive.

Sanggeun may choose a natural number x with 1 ≤ x ≤ n and ask, "Is your number x?" Jeongin then tells him the greatest common divisor of the secret number and x.

Here is one possible conversation when n = 6.

• Sanggeun: Is it 3?
• Jeongin: The gcd of 3 and my number is 1.
• Sanggeun: (So it is neither 3 nor 6; it must be one of 1, 2, 4, 5.) Then is it 2?
• Jeongin: The gcd of 2 and my number is 2.
• Sanggeun: (So it is neither 1 nor 5.) Your number is 4, right?
• Jeongin: The gcd of 4 and my number is 2.
• Sanggeun: Aha, then your number is 2.

In this example Sanggeun asked three questions, but when n = 6 he can always determine Jeongin's number in just two questions.

He can start by asking 6. If the answer is 1, the number is 1 or 5, so one more question settles it; if the answer is 2, it is 2 or 4, and likewise. If the answer is 3 the number is 3, and if it is 6 the number is 6. Hence two questions always suffice.

Given n, determine how many questions Sanggeun needs, in the worst case, to be guaranteed to identify Jeongin's number when he asks optimally.

The first line contains an integer n. (2 ≤ n ≤ 10,000)

Print, on the first line, the maximum number of questions required in the worst case when Sanggeun asks optimally.