問題文

これはインタラクティブな問題です。

T 個のテストケースに対して、以下の問題を解いてください。

長さ N の非負整数列 A = (A_1, A_2, \cdots, A_N) と整数 k (1 \le k \le N) が隠されている。数列 A は以下の条件を満たすことが分かっている。

• 1 \le i \le k-1 のとき A_i \lt A_{i+1}
• k \le i \le N-1 のとき A_i \gt A_{i+1}

整数 N が与えられた後、あなたはクエリを何回か送ることができる。 1 回のクエリでは、 1 \le i \le N なる i を 1 つ指定して A_i の値を得ることができる。できるだけ少ない回数のクエリで数列 A の最大値を求めよ。（詳しくは小課題・得点の項を参照）

制約

• 1 \leq T \leq 50
• 1 \leq N \leq 1500
• 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 入力はすべて整数

小課題・得点

この問題に正解した場合の得点は、以下のように計算されます。

各テストケースに対するクエリの数の最大値を Q_{\mathrm{max}} とします。

• 1500 \lt Q_{\mathrm{max}} のとき 0 点
• 40 \lt Q_{\mathrm{max}} \leq 1500 のとき 1 点
• 22 \lt Q_{\mathrm{max}} \leq 40 のとき 3 点
• 15 \lt Q_{\mathrm{max}} \leq 22 のとき 4 点
• Q_{\mathrm{max}} \leq 15 のとき 7 点

入出力

最初に、テストケースの数 T が与えられます。

T

以降、 T 個のテストケースが続きます。

テストケースの最初では、次の形式で入力が与えられます。

N

クエリを送るには、以下の形式で出力してください。

? i

このクエリに対して、次の形式で返答が与えられます。

A_i

数列 A の最大値を答えるときは、その値を A_{\mathrm{max}} として次の形式で出力してください。

! A_{\mathrm{max}}

その後、次のテストケースがあれば続けて処理し、なければすぐにプログラムを終了してください。

プログラムが正しくないクエリを出力した場合は、 -1 が入力に与えられます。この場合はすぐにプログラムを終了してください。

注意

• この問題のジャッジはアダプティブです。つまり、これまでのクエリの内容に矛盾しない限り、数列の内容が変更される場合があります。
• すべてのテストケースで答えを出力した後、または -1 が与えられた後、プログラムをすぐに終了しなかった場合、採点結果は定義されません。
• 出力のたびに標準出力を flush してください。そうしない場合、TLE の可能性があります。
• AtCoder の仕様上、1 点以上を取れば AC と表示されることにご注意ください。（AC でも満点ではない場合があります）

入出力例1

数列 A は (1, 2, 3, 4, 5, 6, 9, 1) で、 k = 7 です。数列 A の最大値は 9 です。

例えば、 1 回目のクエリ終了時点では (7, 8, 9, 8, 7, 6, 5, 4) を数列 A としてもクエリの内容に矛盾しないので、この数列に変更される可能性があります。

入出力例2