Game on GCD Queries

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 propose a number x_i, and Chikhman will respond with the greatest common divisor (GCD) of this number and his age.

Let's consider the situation when n = 6. Kutsmen begins by proposing $3$, and Chikhman replies with GCD of $1$. This means that Chikhman's age cannot be $3$ or $6$, but could be $1$, $2$, $4$, or $5$. Next, Kutsmen proposes $2$, and Chikhman responds with GCD of $2$. This narrows down Chikhman's possible age to $2$ or $4$, excluding $1$ and $5$. Finally, Kutsmen proposes $4$, and Chikhman replies with $2$. This confirms that Chikhman's age is $2$. Therefore, Kutsmen required $3$ queries.

However, Chikhman's age can actually be determined in just $2$ queries. To do this, Kutsmen should first propose $6$. After the response, the age can be determined with at most one more query.

Find the minimal number of queries Kutsmen needs in the worst-case scenario if he acts optimally.