Гра на запити НСД

У Чіхмана вчора був день народження (насправді ні), і він грав у гру на вгадування з Куцменом: Куцмен намагався вгадати вік Чіхмана. Куцмен знає, що вік Чіхмана — натуральне число від $1$ до $n$ включно. Куцмен може загадати число x_i, і Чіхман відповість найбільшим спільним дільником (НСД) цього числа і свого віку.

Розглянемо випадок, коли n = 6. Куцмен починає з числа $3$, і Чіхман відповідає НСД $1$. Це означає, що вік Чіхмана не може дорівнювати $3$ чи $6$, але може бути $1$, $2$, $4$ або $5$. Далі Куцмен загадує $2$, і Чіхман відповідає НСД $2$. Можливий вік — тільки $2$ або $4$, але не $1$ і не $5$. Нарешті, Куцмен загадує $4$, і Чіхман відповідає $2$. Вік Чіхмана точно $2$. Отже, Куцмену потрібно було $3$ запити.

Втім, дізнатися вік Чіхмана можна й за $2$ запити. Для цього Куцмен має спочатку загадати $6$, і після відповіді з’ясувати вік не більше ніж ще одним запитом.

Знайдіть мінімальну кількість запитів, які Куцмену потрібно зробити у найгіршому випадку, якщо він діє оптимально.