The GCD Guessing Game

Time limit1sMemory limit128 MB

Summary

Given n, find the minimum worst-case number of GCD queries needed to uniquely identify a hidden number between 1 and n using adaptive gcd questions.

Level: Hard8 of 10
Topics: Number theory, Math, Combinatorics
Solved: No attempts yet

Problem

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.

Input

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

Output

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

Examples5

Example 1
Input
```
6
```
Expected output
```
2
```
Example 2
Input
```
2
```
Expected output
```
1
```
Example 3
Input
```
3
```
Expected output
```
2
```
Example 4
Input
```
5
```
Expected output
```
3
```
Example 5
Input
```
10
```
Expected output
```
3
```