D. НОД-угадайка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Загадано некоторое положительное целое число $$$1 \le x \le 10^9$$$.

За один запрос вы можете выбрать два положительных целых числа $$$a \neq b$$$. В качестве ответа на этот запрос вы получите $$$\gcd(x + a, x + b)$$$, где $$$\gcd(n, m)$$$ обозначает наибольший общий делитель чисел $$$n$$$ и $$$m$$$.

Чтобы угадать одно загаданное число $$$x$$$, вы можете совершить не более $$$30$$$ запросов.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Загаданное число $$$x$$$ удовлетворяет следующим ограничениям: ($$$1 \le x \le 10^9$$$).

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

Загаданное число $$$x$$$ зафиксировано до начала взаимодействия и не зависит от ваших запросов.

Для угадывания каждого $$$x$$$ вы можете сделать не более $$$30$$$ запросов следующего вида:

  • «? a b» ($$$1 \le a, b \le 2 \cdot 10^9$$$, $$$a \neq b$$$).

В ответ на этот запрос вы получите $$$\gcd(x + a, x + b)$$$.

Когда вы узнаете число $$$x$$$, выведите одну строку следующего формата:

  • «! x» ($$$1 \le x \le 10^9$$$).

После этого переходите к решению следующего набора входных данных.

Если вы сделаете более $$$30$$$ запросов для одного $$$x$$$, или запросы будут некорректными, взаимодействие будет немедленно прекращено, а ваша программа получит вердикт Неправильный ответ.

После вывода запросов не забудьте выводить символ перевода строки и сбрасывать буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

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

Взломы

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

Первая строка должна содержать одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Первая и единственная строка каждого набора входных данных должна содержать единственное целое число $$$x$$$ ($$$1 \le x \le 10^9$$$) — число $$$x$$$, которое нужно угадать.

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

1

8


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

? 1 2

? 12 4

! 4
? 2000000000 1999999999

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

Первое загаданное число равно $$$4$$$, поэтому ответы на запрос следующие:

«? 1 2» — $$$\gcd(4 + 1, 4 + 2) = \gcd(5, 6) = 1$$$.

«? 12 4» — $$$\gcd(4 + 12, 4 + 4) = \gcd(16, 8) = 8$$$.

Второе загаданное число равно $$$10^9$$$, поэтому ответ на запрос следующий:

«? 2000000000 1999999999» — $$$\gcd(3 \cdot 10^9, 3 \cdot 10^9 - 1) = 1$$$.

Эти запросы показаны только для лучшего понимания протокола взаимодействия, и их недостаточно, чтобы однозначно восстановить $$$x$$$.