F. Угадать количество делителей
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

Загадано число $$$1 \le X \le 10^{9}$$$. Вам не нужно угадывать это число. Вам нужно определить количество делителей этого числа, и даже это вам не нужно делать точно: ваш ответ будет считаться верным, если его абсолютная погрешность не превышает 7 или его относительная погрешность не превышает $$$0.5$$$. Формально, пусть ваш ответ равен $$$ans$$$, а количество делителей $$$X$$$ равно $$$d$$$, тогда ваш ответ будет считаться правильным, если выполнено хотя бы одно из следующих двух условий:

  • $$$| ans - d | \le 7$$$;
  • $$$\frac{1}{2} \le \frac{ans}{d} \le 2$$$.

Вы можете не более $$$22$$$ раз сделать запрос. Запрос состоит из одного целого числа $$$1 \le Q \le 10^{18}$$$. В ответ на запрос вы получите $$$gcd(X, Q)$$$ — наибольший общий делитель $$$X$$$ и $$$Q$$$.

Число $$$X$$$ зафиксировано до всех запросов. Иными словами, интерактор не является адаптивным.

Назовём процесс отгадывания количества делителей числа $$$X$$$ игрой. В рамках одного теста вам нужно будет сыграть $$$T$$$ независимых игр, то есть отгадать количество делителей $$$T$$$ раз для $$$T$$$ независимых чисел $$$X$$$.

Входные данные

На первой строке записано одно целое число $$$T$$$ ($$$1 \le T \le 100$$$) — количество игр.

Протокол взаимодействия

Чтобы сделать запрос, выведите строку вида «? Q» ($$$1 \le Q \le 10^{18}$$$). После запроса считайте одно число — $$$gcd(X, Q)$$$. Вы можете сделать не более $$$22$$$ таких запросов в рамках одной игры.

Если вы считаете, что знаете количество делителей $$$X$$$ с достаточной точностью, выведите ваш ответ в формате «! ans». $$$ans$$$ должно быть целым числом. Если это последняя игра, то вы должны завершить выполнение программы, иначе вы должны начать следующую игру. Обратите внимание, что интерактор не выводит ничего в ответ на вывод ответа.

После вывода запроса или ответа не забудьте вывести перевод строки и сбросить буфер вывода. Для сброса буфера вывода используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.

Взломы

Для взломов используйте следующий формат:

Первая строка содержит одно целое число $$$T$$$ ($$$1 \le T \le 100$$$) — количество игр.

Каждая из следующих $$$T$$$ строк содержит одно целое число $$$X$$$($$$1 \le X \le 10^{9}$$$) — загаданное число.

Так, пример из условия имеет вид 


2
998244353
4194304
Пример
Входные данные
2

1

1

1


1024

1048576

4194304
Выходные данные

? 982306799268821872

? 230856864650023977

? 134690134760714371

! 5
? 1024

? 1048576

? 1073741824

! 42
Примечание

Почему ограничение на запросы именно 22? Возможно, автор задачи — фанат Тейлор Свифт.

Рассмотрим пример из условия.

В первой игре загадано число $$$X = 998\,244\,353$$$. Было бы сложно это угадать, правда? Это число является простым, то есть количество его делителей равно 2. Решение сделало запросы с несколькими случайными числами, и ответы на все запросы оказались равны 1 (удивительно, что ни один из трёх запросов не оказался кратным $$$998\,244\,353$$$). Логично предположить, что у загаданного числа не очень много делителей, поэтому решение ответило 5. Почему бы и не 5. Этот ответ будет засчитан, так как $$$| 5 - 2 | = 3 \le 7$$$.

Во второй игре загадано число $$$X = 4\,194\,304 = 2^{22}$$$, количество его делителей равно 23. Решение сделало запросы $$$1024 = 2^{10}$$$, $$$1\,048\,576 =2^{20}$$$, $$$1\,073\,741\,824 = 2^{30}$$$ и получило ответы $$$1024 = 2^{10}$$$, $$$1\,048\,576 =2^{20}$$$, $$$4\,194\,304 = 2^{22}$$$, соответственно. Затем решение окончательно запуталось и выдало ответ на Главный вопрос жизни, Вселенной и всего такого. Этот ответ будет засчитан, так как $$$\frac{1}{2} \le \frac{42}{23} \le 2$$$.