這是一個互動式問題。

Ivan 想出了戰艦遊戲的新規則！

• 遊戲在一個 $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"，其中：

• 若棋盤上沒有空的 $2 \times 2$ 正方形，則 $x = -1, y = -1$。
• 否則，$1 \le x, y \le n - 1$，且由格子 $(x, y), (x + 1, y), (x, y + 1), (x + 1, y + 1)$ 組成的正方形是空的。

如果你的答案不正確，你將會收到一行值為 $-1$ 的回應，此時你應該終止程式。否則，你將會收到一行值為 $1$ 的回應，接著你應該進行下一場遊戲（如果這是最後一場遊戲，則結束程式）。

保證所有遊戲的 $n$ 之總和不超過 $5000$。 保證每場遊戲的棋盤是固定的，且互動器不是自適應的。 如果你沒有輸出任何內容或忘記刷新輸出（flush），你的程式將會得到 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$ 正方形。