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$ までの任意の整数）。どの2隻の船も、辺または角で隣接してはいけません。

その後、後攻プレイヤーがゲームを開始します。

• 後攻プレイヤーはボードのサイズ $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$ を超えないことが保証されています。 各ゲームにおけるボードは固定されており、インタラクタは適応型ではないことが保証されています。 何も出力しなかったり、出力をフラッシュし忘れたりすると、あなたのソリューションは 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番目のゲームのボード。

最初のゲームでは、ボード上に空の $2 \times 2$ の正方形はありません。 2番目のゲームでは、ボード上に空の $2 \times 2$ の正方形がちょうど1つ存在します。