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

海よ、また会えたね。次の夏休みも幸せでありますように！ とても昔、ウナとカモメはもう良い友人だった。

彼らはゲームをするのが好きだった。前回、ウナが発明したゲームはカモメの優れた戦略で簡単に解かれた。今回は、ウナが新しいゲームを持ってきた。

ウナは $n$ 個のノードを持つ木を考えている。カモメは最大 $n$ 回のクエリを行うことができる：

• カモメは順列 $P_1, P_2, \dots, P_n$（ただし $0 \le P_i \le n-1$ であり、すべての $P_i$ は互いに異なる）をウナに伝えることができる。するとウナは、ノード $i$ に重み $2^{P_i}$ が割り当てられたときの木の重み付き直径の長さをカモメに教えてくれる。

しかし時々、カモメはウナがトラブルを起こしていることに気づく。より具体的には、どんなに質問しても木を確実に決定できない場合がある。そのような場合、カモメは解がないと報告できる。

インタラクション

この問題はインタラクティブ問題です。各出力の後には必ず出力バッファをフラッシュしてください。出力バッファをフラッシュするには、以下を使用できます：

• C/C++: fflush(stdout) または cout.flush()
• Java および Kotlin: System.out.flush()
• Python: sys.stdout.flush()

まず、テストケースの数 $T$ ($1 < T < 10^4$) を読み込んでください。 各テストケースごとに、木のサイズ $n$ ($2 \le n \le 100$, $\sum n^2 < 10^6$) を読み込んでください。

クエリを行うには、"? $P_1 P_2 \dots P_n$" の形式で1行を出力してください（ただし $0 \le P_i \le n-1$ であり、$1 < i < j \le n$ のとき $P_i \ne P_j$）。 その後、2進表現による木の直径重みを表す $n$ 文字からなる文字列を読み込みます。クエリが無効であるか、1つのテストケースで $n$ 回より多いクエリを行った場合、ジャッジプログラムは -1 を出力します。-1 を読み込んだら、未定義動作を避けるために即座に終了しなければなりません。

木を一意に決定することが不可能と判断された場合は、"! NO" を出力してください。 そうでない場合は、木に辺 $(u_i, v_i)$ が含まれることを示す "! YES $u_1 v_1 u_2 v_2 \dots u_{n-1} v_{n-1}$" の形式で1行を出力してください。辺は任意の順序で出力できます。

その後、答えが正しいかどうかを示す "OK" または "WA" という単語を読み込みます。"WA" を読み込んだら、未定義動作を避けるために即座に終了しなければなりません。 木が決定不可能であるにもかかわらず YES を出力し、答えが正しかったとしても、ウナはあなたが不正をしていると考えるため、答えは誤答とみなされます。

ジャッジプログラムは適応型ではないため、クエリ後も答えは変更されません。

入出力例

入力 1

2
4
1110
1110
OK
3
111
OK

出力 1

? 0 1 2 3
? 2 1 0 3
! YES 1 4 2 4 3 4
? 0 1 2
! NO

注記

テストツールが提供されており、参加者がソリューションを開発・テストできます。このツールは添付ファイルからダウンロードできます。"-h" オプションでツールを実行すると使い方が説明されます。テストツールは実際のジャッジプログラムの一部の機能のみを実装しており、一部のテストシナリオのみを実装しています。