Это интерактивная задача.
Загадано число \(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\).
Протокол взаимодействия
Чтобы сделать запрос, выведите строку вида «? 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
Примечание
Почему ограничение на запросы именно 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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1
1
1
1024
1048576
4194304
|
? 982306799268821872
? 230856864650023977
? 134690134760714371
! 5
? 1024
? 1048576
? 1073741824
! 42
|