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

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

У нас есть секретная линейка, на которой отсутствует одно число $$$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{7}$$$ запросов.

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

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

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

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

Если ваша программа сделает более $$$7$$$ запросов для одного набора входных данных, сделает недопустимый запрос или выведет неправильное значение $$$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$$$) — отсутствующее число на линейке.