Game on NSD Requests
Chikhman's birthday was yesterday (though not really), and he played a guessing game with Kutsmen: Kutsmen tried to guess Chikhman's age. Kutsmen knows that Chikhman's age is a natural number between 1 and n, inclusive. Kutsmen can suggest a number x[i], and Chikhman will respond with the GCD of this number and his age.
Let's explore the scenario when n = 6. Kutsmen begins by asking about 3, and Chikhman replies with a GCD of 1. This indicates that Chikhman's age cannot be 3 or 6, but it could be 1, 2, 4, or 5. Next, Kutsmen asks about 2, and Chikhman responds with a GCD of 2. This narrows down Chikhman's age to either 2 or 4, excluding 1 and 5. Finally, Kutsmen proposes the number 4, and Chikhman replies with 2. This confirms that Chikhman's age is 2. Therefore, Kutsmen required 3 queries.
However, Chikhman's age can be determined in just 2 queries. To achieve this, one should initially ask about 6. Based on the response, Chikhman's age can be pinpointed with at most one additional query.
Determine the minimum number of queries Kutsmen needs to make in the worst-case scenario if he plays optimally.
Input
The first line contains a single integer n (2 ≤ n ≤ 10^7) – the maximum possible age of Chikhman.
Output
Output a single number – the minimum number of queries needed to guess Chikhman's age.