この問題は インタラクティブな問題（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。
正整数 \(N\) が与えられます。\(\\ \) ジャッジシステムが長さ \(2N\) の正整数列 \(A = (A_1, A_2, \dots, A_{2N})\) を隠し持っています。\(\\ \) \(A\) は \(1,2,\dots,N\) をそれぞれちょうど \(2\) 個ずつ含みます。
あなたは以下の質問を \(20\) 回まで行うことが出来ます。
\(A_x = A_y~(1 \leq x \lt y \leq 2N)\) であるような正整数 \(x, y\) を \(1\) つ特定してください。
\(1\) つの入力につき、\(T\) 個のテストケースが与えられます。
この問題は インタラクティブな問題（あなたの作成したプログラムとジャッジシステムが入出力を介して対話を行う形式の問題）です。
最初にテストケース数 \(T\) を標準入力から以下の形式で受け取ってください。
| \(T\) |
その後、各テストケースについて、以下に示す入出力を行ってください。
各テストケースについて、\(N\) を標準入力から以下の形式で受け取ってください。
| \(N\) |
\(A_x = A_y~(1 \leq x \lt y \leq 2N)\) であるような正整数 \((x, y)\) を \(1\) つ特定できるまで質問を繰り返してください。質問は、以下の形式で標準出力に出力してください。
| ? \(l~r\) |
これに対する応答は、以下の形式で標準入力から与えられます。
| \(K\) |
\(A_x = A_y~(1 \leq x \lt y \leq 2N)\) であるような正整数 \((x, y)\) を \(1\) つ特定できたら、以下の形式で標準出力に出力してください。
| ! \(x~y\) |
ここで、出力形式にミスがあった場合、質問回数が \(20\) 回を超えた場合、前回のテストケースで解答した \(x, y\) が条件を満たしていなかった場合は、それ以降の \(N\) や \(K\) は与えられず、文字列 -1 が標準入力から与えられます。この場合、ただちにプログラムを終了してください。
\(N=3\)、\(A = (1,3,1,2,3,2)\) の場合の入出力例です。
| 入力 | 出力 | 説明 |
| 3 | はじめに \(T\) が標準入力から与えられます。 | |
| 3 | \(N\) が標準入力から与えられます。 | |
| ? 1 3 | \((l,r) = (1,3)\) として質問します。 | |
| 2 | \(A_1, A_2, A_3\) に現れる相異なる値は \(1,3\) の \(2\) つとなるため、ジャッジはその値を返します。 | |
| ? 5 5 | \((l,r) = (5,5)\) として質問します。 | |
| 1 | \(A_5\) に現れる相異なる値は \(3\) の \(1\) つとなるため、ジャッジはその値を返します。 | |
| ! 4 6 | \((x,y) = (4,6)\) として解答します。解答した場合、ただちに次のテストケースに進む必要があります。 | |
| 3 | \(2\) つ目のテストケースに対する \(N\) が標準入力から与えられます。 | |
| ! 4 5 | \((x,y) = (4,5)\) として解答します。\(A_4 = 2\)、\(A_5 = 3\) のためのこの解答は不正解となります。 | |
| -1 | 前回のテストケースで不正解であったため、-1 が標準入力から与えられます。 | |
| 以降の \(N,K\) が入力されることはありません。ただちにプログラムを終了させる必要があります。 |