Линде нравится красить волосы в разные цвета время от времени, и ей приятно, когда её парень Арчи замечает разницу между предыдущим и новым цветом. Арчи высказывает своё мнение тогда и только тогда, если он замечает разницу — поэтому Линда всегда знает, заметил ли Арчи разницу или нет.
Недавно в продаже появился новый бренд краски для волос, где все доступные цвета пронумерованы числами от $$$1$$$ до $$$N$$$, причём меньшая разница между номерами означает менее заметную разницу в цветах.
Линда знает, что существует определённая критическая разница $$$C$$$ ($$$1 \le C \le N$$$), такая, что Арчи замечает различие между цветами между текущим цветом $$$\mathrm{color}_{\mathrm{new}}$$$ и предыдущим цветом $$$\mathrm{color}_{\mathrm{prev}}$$$, если $$$\left|\mathrm{color}_{\mathrm{new}} - \mathrm{color}_{\mathrm{prev}}\right| \ge C$$$ и не замечает, если $$$\left|\mathrm{color}_{\mathrm{new}} - \mathrm{color}_{\mathrm{prev}}\right| < C$$$.
Теперь Линда купила $$$N$$$ упаковок краски для волос нового бренда, по одной каждого цвета от $$$1$$$ до $$$N$$$, и готова организовать эксперимент. Линда собралась регулярно перекрашивать цвет своих волос и наблюдать за реакцией Арчи, заметит ли он разницу в цвете, или нет. Так как для хорошей покраски каждую упаковку нужно израсходовать полностью, каждый из цветов можно использовать ровно один раз.
Перед началом эксперимента, Линда использовала краску другого бренда, который не совместим с новым, поэтому для корректности эксперимента нужно принять, что реакция Арчи на первый использованный новый цвет ничего не означает.
Цель Линды — узнать точное значение $$$C$$$, используя ограниченное количество перекрасок. Напишите программу, которая находит значение $$$C$$$, экспериментируя с данными $$$N$$$ цветами и наблюдая за реакциями Арчи на изменения цвета.
Это интерактивная задача. В начале дано одно целое число $$$T$$$ ($$$1 \leq T \leq 100$$$), количество примеров в одном тесте.
Для каждого тестого примера, ввод содержит одно целое число, значение $$$N$$$ ($$$1 < N \le 10^{18}$$$). Значение $$$C$$$ держится в секрете тестирующей системой.
Ваша программа должна задавать запросы в следующем формате: «? $$$P$$$», где $$$P$$$ целое число ($$$1 \le P \le N$$$), которое обозначает следующий используемый цвет. Тестирующая система даст ответ в следующей строке ввода. Ответ равен $$$1$$$, если Арчи заметил разницу между последними двумя цветами, и $$$0$$$ иначе. Никакие два запроса не должны использовать одно и то же значение $$$P$$$.
Когда ваша программа определит $$$C$$$, она должна вывести её значение в следующем формате: «= $$$C$$$». Тестирующая система не будет отвечать на такой вывод и перейдёт к выполнению следующего примера.
Ваша программа может использовать не более 64 запросов «?» для каждого тестового примера, чтобы определить значение $$$C$$$.
Чтобы установить правильное выполнение протокола между вашей программой и тестирующей системой, вы должны сбросить буфер вывода после каждого запроса.
Команда std::endl записывает новую строку и сбрасывает буфер вывода.
Примите во внимание, что возможно получить вердикт «Output isn't correct» даже после вывода правильного ответа, в случае, если ограничения задачи были нарушены во время выполнения программы. Нарушения протокола могут закончится вердиктом «Execution killed».
Для запуска решения на личном тесте вначале запишите «$$$T$$$» в первой строке, и затем используйте формат «$$$N$$$ $$$C$$$» на одной строке для каждого из $$$T$$$ примеров.
Подзадачи:
1 7 1 1 0 0 1
? 2 ? 7 ? 4 ? 1 ? 5 = 4
Примечания к данному тесту по каждой строчке ввода:
