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

Мистер 1048576 — один из тех преподавателей, который ненавидит тратить время на ведение посещаемости. Вместо того чтобы вести посещаемость традиционным способом, он решил попробовать что-то новое сегодня.

В его классе $$$n$$$ студентов с номерами от $$$1$$$ до $$$n$$$. Он точно знает, что сегодня отсутствует ровно $$$1$$$ студент. Чтобы определить, кто отсутствует, он может задать некоторые запросы классу. В каждом запросе он может указать два целых числа $$$l$$$ и $$$r$$$ ($$$1\leq l\leq r\leq n$$$), и все студенты, чьи номера от $$$l$$$ до $$$r$$$ (включительно), поднимут руки. Затем он подсчитывает их, чтобы определить, лежит ли номер отсутствующего студента между этими значениями.

Все было хорошо, пока его ассистент не заметил что-то странное — студенты нечестные! Некоторые студенты, чьи номера находятся в указанном диапазоне, могут не поднимать руки, в то время как другие студенты, чьи номера не находятся в указанном диапазоне, могут поднять руки и дать прокси-посещаемость за кого-то другого. Но они не хотят вызывать подозрений. Таким образом, возможны только следующие $$$4$$$ случая для конкретного запроса $$$(l,r)$$$ —

1. Истинно положительный: присутствуют $$$r-l+1$$$ студент и $$$r-l+1$$$ студент подняли руки.
2. Истинно отрицательный: присутствуют $$$r-l$$$ студентов и $$$r-l$$$ студентов подняли руки.
3. Ложно положительный: присутствуют $$$r-l$$$ студентов, но $$$r-l+1$$$ студент поднял руку.
4. Ложно отрицательный: присутствуют $$$r-l+1$$$ студент, но $$$r-l$$$ студентов поднял руку.

В первых двух случаях студенты считаются отвечающими честно, в то время как в последних двух случаях студенты считаются отвечающими нечестно. Студенты могут взаимно решить свою стратегию, неизвестную мистеру 1048576. Кроме того, студенты не хотят вызывать подозрений и в то же время хотят создать много путаницы. Поэтому их стратегия всегда соответствует следующим двум условиям —

1. Студенты никогда не будут отвечать честно $$$3$$$ раза подряд.
2. Студенты никогда не будут отвечать нечестно $$$3$$$ раза подряд.

Мистер 1048576 раздосадован таким поведением студентов. Поэтому он готов отметить как минимум $$$2$$$ студентов как отсутствующих (хотя он знает, что отсутствует только один). Посещаемость считается успешной, если отсутствующий студент находится среди этих двух. Кроме того, из-за ограниченного времени на занятия, он может задать не более $$$\lceil\log_{1.116}{n}\rceil-1$$$ запросов (странное число, но ладно). Помогите ему завершить успешную посещаемость.

Сначала прочтите строку, содержащую одно целое число $$$t$$$ ($$$1\leq t\leq 2048$$$), обозначающее количество независимых тестов, которые вы должны решить.

Для каждого теста сначала прочтите строку, содержащую одно целое число $$$n$$$ ($$$3\leq n\leq 10^5$$$). Затем вы можете задать до $$$\lceil\log_{1.116}{n}\rceil-1$$$ запросов.

Чтобы задать запрос, напечатайте одну строку в формате "? l r" (без кавычек) $$$(1\leq l\leq r\leq n)$$$. Затем прочтите одну строку, содержащую одно целое число $$$x$$$ ($$$r-l\leq x\leq r-l+1$$$), обозначающее количество студентов, поднявших руки в ответ на запрос.

Чтобы отметить студента как отсутствующего, напечатайте одну строку в формате "! a" (без кавычек) $$$(1\leq a\leq n)$$$. Затем прочтите одно целое число $$$y$$$ ($$$y\in\{0,1\}$$$). Если студент с номером $$$a$$$ отсутствовал, $$$y=1$$$, в противном случае, $$$y=0$$$. Обратите внимание, что эта операция не считается запросом, но вы можете выполнить эту операцию не более $$$2$$$ раз.

Чтобы завершить тест, напечатайте одну строку в формате "#" (без кавычек). Затем вы должны продолжить решать оставшиеся тесты.

Обратите внимание, что если вы зададите больше запросов, или запрос будет невалидным — вы получите вердикт Wrong answer.

Гарантируется, что сумма $$$n$$$ по всем тестам не превышает $$$10^5$$$.

После вывода ответов не забудьте вывести конец строки и очистить буфер вывода. В противном случае вы получите вердикт Idleness limit exceeded. Чтобы очистить буфер, используйте:

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

Формат ввода для взломов

Тесты для этой задачи используют как неадаптивные, так и адаптивные тесты. Вы можете использовать неадаптивный тест для проведения взломов.

Первая строка ввода содержит одно целое число $$$t$$$ ($$$1\leq t\leq 2048$$$).

Первая строка каждого теста содержит три целых числа $$$g$$$, $$$n$$$ и $$$x$$$, где $$$g=1$$$ (для идентификации того, что этот тест должен использовать неадаптивный алгоритм), $$$n$$$ ($$$3\leq n\leq 10^5$$$) означает количество студентов в классе, и $$$x$$$ ($$$1\leq x\leq n$$$) означает номер студента, который отсутствует. Вы должны учесть, что сумма $$$n$$$ по всем тестам не превышает $$$10^5$$$.

Вторая строка каждого теста содержит одну строку $$$S$$$ ($$$1\leq\vert S\vert\leq 120, S_i\in \{\texttt{T},\texttt{F}\}$$$). Эта строка представляет последовательность истины. Если $$$S_{(i-1)\bmod \vert S\vert+1}= \texttt{T}$$$, студенты будут действовать честно во время $$$i$$$-го запроса, в противном случае они будут действовать нечестно. Вы также должны учесть, что не должно быть индекса $$$i$$$, для которого $$$S_{(i-1)\bmod \vert S\vert+1} = S_{i\bmod \vert S\vert+1} = S_{(i+1)\bmod \vert S\vert+1}$$$.