Иван придумал новые правила для игры в «Морской бой»!

• Игра проходит на доске размера $n \times n$.
• Первый игрок выбирает целое число $k$ ($n \le k \le \lfloor \frac{n}{2} \rfloor^2$).
• После этого первый игрок расставляет $k$ кораблей на доске так, чтобы количество занятых кораблями клеток было максимально возможным (среди всех допустимых расстановок $k$ кораблей любых размеров).
• Каждый корабль представляет собой прямоугольник размера $1 \times a$ или $a \times 1$ ($a$ — любое целое число от $1$ до $n$ включительно). Любые два корабля не должны иметь общих соседних клеток (ни по стороне, ни по углу).

После этого второй игрок начинает свою игру.

• Второй игрок знает только размер доски $n$.
• Второй игрок может сделать запрос: занята ли клетка $(x, y)$ каким-либо кораблем?
• Второй игрок должен найти любой пустой квадрат $2 \times 2$ на доске или сообщить, что таких квадратов нет.

Второй игрок может сделать не более $6n$ запросов. Пожалуйста, сыграйте за второго игрока и выиграйте игру!

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

Первая строка содержит единственное целое число $t$ ($1 \le t \le 100$) — количество игр. Вы должны сыграть $t$ игр и после этого завершить взаимодействие.

В начале игры вам дается единственное целое число $n$ ($3 \le n \le 1000$) — размер доски.

После этого вы можете делать запросы. Чтобы сделать запрос, выведите одну строку «? $x$ $y$» ($1 \le x, y \le n$) — координаты клетки. Вы получите ответ $c$:

• Если $c = -1$, вы сделали слишком много запросов. Вы должны завершить программу.
• Если $c = 0$, клетка $(x, y)$ пуста.
• Если $c = 1$, клетка $(x, y)$ занята каким-то кораблем.

Чтобы завершить игру, выведите одну строку «! $x$ $y$», где:

• $x = -1, y = -1$, если на доске нет пустых квадратов $2 \times 2$.
• В противном случае $1 \le x, y \le n - 1$, и квадрат с клетками $(x, y), (x + 1, y), (x, y + 1), (x + 1, y + 1)$ пуст.

Если ваш ответ неверен, вы получите строку со значением -1, и вы должны завершить программу. В противном случае вы получите строку со значением 1, и вы должны сыграть следующую игру (или завершить программу, если это была последняя игра).

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

Гарантируется, что доска в каждой игре фиксирована, а интерактор не является адаптивным.

Ваше решение получит вердикт Idleness Limit Exceeded, если вы ничего не выведете или забудете сбросить буфер вывода.

Примеры

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

2
3
0
1
4
0
1
1

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

? 2 1
! -1 -1
? 1 3
? 4 3
! 2 2

Примечание

Доски из первого примера показаны на рисунках ниже. Строки соответствуют координатам $x$, столбцы соответствуют координатам $y$.

Доска из первой игры. Доска из второй игры.

В первой игре на доске нет пустых квадратов $2 \times 2$.

Во второй игре на доске есть ровно один пустой квадрат $2 \times 2$.