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

Kevinには $n$ 人のクラスメートがおり、それぞれ $1, 2, \dots, n$ と番号が振られています。任意の2人は友人であるか、友人ではないかのいずれかです。

Kevinは $2k$ 人のクラスメートを選んで $k$ 個のチームを作りたいと考えています。各チームはちょうど2人からなり、各人は最大で1つのチームにしか所属できません。

$i$ 番目のチームの2人を $u_i, v_i$ とします。チーム形成時の潜在的な対立を避けるため、チームのメンバーは以下の2つの条件のいずれかを満たす必要があります。

• すべての $i$ ($1 \le i \le k$) について、クラスメート $u_i$ と $v_i$ は友人である。
• すべての $i$ ($1 \le i \le k$) について、クラスメート $u_i$ と $v_i$ は友人ではない。

Kevinは、$n$ 人の間の友人関係がどのようなものであっても、常に $2k$ 人を見つけてチームを作ることができるような最大の $k$ を求めたいと考えています。その後、実際に $k$ 個のチームを作る必要があります。しかし、2人のクラスメートが友人かどうかを尋ねるのは気まずいため、Kevinは最大 $n$ 組のクラスメートの友人関係について尋ねることでこれを達成したいと考えています。

インタラクタは適応的（adaptive）です。これは、隠されたクラスメート間の関係が対話の前に固定されているわけではなく、対話中に変化する可能性があることを意味します。

インタラクション

各テストケースには複数のテストケースが含まれます。最初の行にはテストケースの数 $t$ ($1 \le t \le 10^4$) が含まれます。 続いて各テストケースの説明が続きます。

各テストケースの最初の行には、正の整数 $n$ ($2 \le n \le 10^5$) が含まれます。これはクラスメートの人数です。

まず、形成できるチームの最大数である整数 $k$ ($1 \le k \le \frac{n}{2}$) を出力してください。

クエリは以下の形式で行うことができます。? u v と出力してください（ここで $1 \le u \neq v \le n$）。その後、単一の整数を読み取ります。0または1が返され、彼らが友人であるかどうかを示します。1は友人であることを、0は友人ではないことを意味します。

答えを出力したい場合は、! u1 v1 u2 v2 . . . uk vk と出力してください。ちょうど $2k$ 個の異なる数値を出力する必要があります。その後、対話は次のテストケースへ進みます。

最大 $n$ 回までクエリを行うことができます。答えを出力することはクエリ回数にはカウントされません。 すべてのテストケースを通じた $n$ の合計は $10^5$ を超えないことが保証されています。

各クエリを出力した後、必ず改行し、出力をフラッシュ（flush）してください。そうしないと、Idleness limit exceeded という判定を受ける可能性があります。

対話の途中で有効なデータの代わりに $-1$ を読み取った場合、プログラムは直ちに終了しなければなりません。これは、無効なクエリやその他のミスにより Wrong answer を受け取ることを意味します。終了しなかった場合、プログラムは閉じられたストリームを読み続けることになるため、任意の判定結果となる可能性があります。

ハック

ハック用のインタラクタは適応的ではありません。ハックを行うには、以下の形式を使用してください。

最初の行には manual という単語が含まれます。 2行目には単一の整数 $t$ ($1 \le t \le 10^4$) が含まれます。 各テストケースの最初の行には整数 $n$ ($2 \le n \le 10^5$) が含まれます。 各テストケースの2行目には、長さ $\frac{n(n-1)}{2}$ の '0' と '1' からなる文字列 $s$ が含まれます。これは $(1, 2), (1, 3), \dots, (1, n), (2, 3), (2, 4), \dots, (2, n), \dots, (n-1, n)$ の関係を示します。'1' は友人であることを、'0' は友人ではないことを意味します。

すべてのテストケースを通じた $n$ の合計は $10^5$ を超えてはなりません。 ハックには追加の制約があります：すべてのテストケースを通じた $\frac{n(n-1)}{2}$ の合計は $10^7$ を超えてはなりません。

入出力例

入力 1

2
3
1
5
1
0
1
0
0

出力 1

1
? 1 2
! 1 2
2
? 1 2
? 3 4
? 3 5
? 1 3
? 2 4
! 1 2 3 5

注記

最初のテストケースにおいて： Kevinは3人の間の友人関係がどうであれ、1つのチームを作れると主張します。 Kevinは人1と人2の友人関係について尋ねます。審査員は彼らが友人であると回答します。 Kevinは人1と人2でチームを作れると回答します。

2番目のテストケースにおいて： Kevinは5人の間の友人関係がどうであれ、2つのチームを作れると主張します。 Kevinは人(1, 2), (3, 4), (3, 5), (1, 3), (2, 4) の友人関係について尋ねます。審査員は 1, 0, 1, 0, 0 と回答します。 Kevinは人(1, 2)と(3, 5)で2つのチームを作れると回答します。 人(1, 3)と(2, 4)で2つのチームを作ることも可能です。なぜなら、どちらも友人ではないからです。