G1. Линейка (лёгкая версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это легкая версия задачи. Единственное отличие между двумя версиями заключается в том, что в этой версии вы можете сделать не более $$$\mathbf{10}$$$ запросов.

Это интерактивная задача. Если вы не уверены, как работают интерактивные задачи, рекомендуется прочитать руководство для участников.

У нас есть секретная линейка, на которой отсутствует одно число $$$x$$$ ($$$2 \leq x \leq 999$$$). Когда вы измеряете объект длиной $$$y$$$, линейка сообщает следующие значения:

  • Если $$$y < x$$$, линейка (правильно) измеряет объект как имеющий длину $$$y$$$.
  • Если $$$y \geq x$$$, линейка неправильно измеряет объект как имеющий длину $$$y+1$$$.

Линейка выше не имеет числа $$$4$$$, поэтому она правильно измеряет первый отрезок как длину $$$3$$$, но неправильно измеряет второй отрезок как длину $$$6$$$, хотя на самом деле он равен $$$5$$$.

Вам нужно найти значение $$$x$$$. Для этого вы можете делать запросы следующего вида:

  • $$$\texttt{?}~a~b$$$ — в ответ мы измерим стороны прямоугольника $$$a \times b$$$ с помощью нашей линейки и умножим результаты, сообщив вам измеренную площадь прямоугольника. Например, если $$$x=4$$$ и вы запрашиваете прямоугольник $$$3 \times 5$$$, мы измерим его стороны как $$$3 \times 6$$$ и сообщим вам $$$18$$$.

Найдите значение $$$x$$$. Вы можете задать не более $$$\mathbf{10}$$$ запросов.

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

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

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

Для каждого набора нет начального ввода. Вы должны начать взаимодействие, задав запрос.

Чтобы сделать запрос, выведите одну строку формата $$$\texttt{?}~a~b$$$ ($$$1 \leq a, b \leq 1000$$$). В ответ вам будет сообщена измеренная площадь прямоугольника согласно нашей секретной линейке.

Когда вы будете готовы вывести ответ, выведите одну строку формата $$$\texttt{!}~x$$$ ($$$2 \leq x \leq 999$$$). После этого продолжайте обрабатывать следующий набор или завершите программу, если это был последний набор. Печать ответа не считается запросом.

Интерактор не адаптивен, что означает, что ответ известен до того, как участник задаст запросы, и не зависит от запросов, заданных участником.

Если ваша программа сделает более $$$10$$$ запросов для одного набора входных данных, сделает недопустимый запрос или выведет неправильное значение $$$x$$$, то ответ на запрос будет $$$-1$$$. После получения такого ответа ваша программа должна немедленно завершиться, чтобы получить вердикт Неправильный ответ. В противном случае вы можете получить произвольный вердикт, поскольку ваше решение продолжит чтение из закрытого потока.

После вывода запроса не забудьте вывести конец строки и сбросить вывод. В противном случае вы можете получить вердикт Превышен лимит бездействия. Для этого используйте:

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

Взломы

Чтобы сделать взлом, используйте следующий формат.

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

Единственная строка каждого набора должна содержать одно целое число $$$x$$$ ($$$2 \leq x \leq 999$$$) — отсутствующее число на линейке.

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

18

25


9999
Выходные данные
? 3 5

? 4 4

! 4
? 99 100

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

В примере взаимодействие происходит следующим образом.

РешениеЖюриОбъяснение
$$$\texttt{2}$$$Есть 2 набора входных данных.
$$$\texttt{? 3 5}$$$$$$\texttt{18}$$$Тайно жюри выбрало $$$x=4$$$. Решение запрашивает прямоугольник $$$3 \times 5$$$, и жюри отвечает $$$3 \times 6 = 18$$$, как описано в условии.
$$$\texttt{? 4 4}$$$$$$\texttt{25}$$$Решение запрашивает прямоугольник $$$4 \times 4$$$, который жюри измеряет как $$$5 \times 5$$$ и отвечает $$$25$$$.
$$$\texttt{! 4}$$$Решение каким-то образом определило, что $$$x=4$$$, и выводит его. Поскольку вывод правильный, жюри переходит к следующему набору.
$$$\texttt{? 99 100}$$$$$$\texttt{1}$$$Тайно жюри выбрало $$$x=100$$$. Решение запрашивает прямоугольник $$$99 \times 100$$$, который жюри измеряет как $$$99 \times 101$$$ и отвечает $$$9999$$$.
$$$\texttt{! 100}$$$Решение каким-то образом определило, что $$$x=100$$$, и выводит его. Поскольку вывод правильный и больше нет наборов, жюри и решение завершают работу.

Обратите внимание, что переносы строк в примерах ввода и вывода сделаны для ясности и не происходят в реальном взаимодействии.