To jest zadanie interaktywne.

Ivan wymyślił nowe zasady gry w statki!

• Gra toczy się na planszy $n \times n$.
• Pierwszy gracz wybiera liczbę całkowitą $k$ ($n \le k \le \lfloor \frac{n}{2} \rfloor^2$).
• Następnie pierwszy gracz rozmieszcza $k$ statków na planszy tak, aby liczba zajętych przez nie pól była maksymalna możliwa (spośród wszystkich poprawnych rozmieszczeń $k$ statków dowolnych rozmiarów).
• Każdy statek musi być prostokątem o rozmiarze $1 \times a$ lub $a \times 1$ (gdzie $a$ jest dowolną liczbą całkowitą od $1$ do $n$ włącznie). Żadne dwa statki nie mogą mieć sąsiadujących pól (zarówno bokami, jak i rogami).

Następnie swoją grę rozpoczyna drugi gracz.

• Drugi gracz zna tylko rozmiar planszy $n$.
• Drugi gracz może zadać pytanie: czy pole $(x, y)$ jest zajęte przez jakiś statek?
• Drugi gracz powinien znaleźć dowolny pusty kwadrat $2 \times 2$ na planszy lub stwierdzić, że takie kwadraty nie istnieją.

Drugi gracz może zadać co najwyżej $6n$ pytań. Zagraj jako drugi gracz i wygraj grę!

Interakcja

Pierwsza linia zawiera pojedynczą liczbę całkowitą $t$ ($1 \le t \le 100$) — liczbę gier do rozegrania. Powinieneś rozegrać $t$ gier, a następnie zakończyć interakcję.

Na początku każdej gry otrzymujesz pojedynczą liczbę całkowitą $n$ ($3 \le n \le 1000$) — rozmiar planszy.

Następnie możesz zadawać pytania. Aby zadać pytanie, wypisz w pojedynczej linii "? x y" ($1 \le x, y \le n$) — współrzędne pola. Otrzymasz odpowiedź $c$:

• Jeśli $c = -1$, zadałeś zbyt wiele pytań. Powinieneś zakończyć działanie programu.
• Jeśli $c = 0$, pole $(x, y)$ jest puste.
• Jeśli $c = 1$, pole $(x, y)$ jest zajęte przez statek.

Aby zakończyć grę, wypisz w pojedynczej linii "! x y", gdzie:

• $x = -1, y = -1$, jeśli na planszy nie ma żadnego pustego kwadratu $2 \times 2$.
• W przeciwnym razie $1 \le x, y \le n - 1$, a kwadrat o wierzchołkach $(x, y), (x + 1, y), (x, y + 1), (x + 1, y + 1)$ jest pusty.

Jeśli Twoja odpowiedź jest błędna, otrzymasz linię z wartością -1 i powinieneś zakończyć działanie programu. W przeciwnym razie otrzymasz linię z wartością 1 i powinieneś rozegrać kolejną grę (lub zakończyć program, jeśli była to ostatnia gra).

Gwarantuje się, że suma $n$ dla wszystkich gier nie przekracza $5000$. Gwarantuje się, że plansza w każdej grze jest ustalona, a interaktor nie jest adaptacyjny. Twoje rozwiązanie otrzyma werdykt Idleness Limit Exceeded, jeśli nic nie wypiszesz lub zapomnisz opróżnić bufor wyjściowy.

Przykład

Wejście 1

2
3
0
1
4
0
1
1

Wyjście 1

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

Uwagi

Plansze z pierwszego testu pokazano na poniższych rysunkach. Wiersze odpowiadają współrzędnym $x$, kolumny odpowiadają współrzędnym $y$.

Plansza z pierwszej gry. Plansza z drugiej gry.

W pierwszej grze na planszy nie ma żadnych pustych kwadratów $2 \times 2$. W drugiej grze na planszy znajduje się dokładnie jeden pusty kwadrat $2 \times 2$.