$N$ 人の自転車競技選手 $1, \dots, N$ がいる。各選手は $1$ から $N$ までの異なるスキルを持っており、2人の選手が対戦する場合、常にスキルが高い選手が勝利する。

選手たちは競技に参加することを好む。競技では、選手たちは環状のリストに並べられる。競技はラウンド形式で行われる。各ラウンドにおいて、各選手は隣接する選手とレースを行い、両隣の選手に負けた場合、その選手は敗退する。

あなたは各選手のスキルを知らないが、それを特定したいと考えている。あなたは全選手を対象とした競技を開催することができ、その都度環状リストの並び順を選択できる。各競技の後、各選手が何ラウンド目で敗退したかを知らされる。

最適な回数の競技を行って選手のスキルを特定せよ。また、部分点として $N$ 回の競技で特定することも可能である。

インタラクション

各テストケースは複数のテストから構成される。インタラクションは、テストケースの数を示す整数 $T$ ($1 \le T \le 10^4$) が含まれる行から始まる。

各テストケースは、選手数を示す整数 $N$ ($3 \le N \le 300$) が含まれる行から始まる。

その後、競技を開催することができる。競技を開催するには、? a1 a2 ... an という形式の行を出力する。ここで $a_k$ は、選手リストの $k$ 番目の位置にいる選手を表す。リスト $a_1, \dots, a_n$ は $1, \dots, n$ の順列でなければならない。

クエリに対する回答は r1 r2 ... rn という形式の行で与えられる。ここで $r_k$ は $0 \le r_k < n$ を満たす。$r_k > 0$ の場合、それは $k$ 番目の位置にいた選手が競技の $r_k$ ラウンド目で敗退したことを示す。$r_k = 0$ の場合、その選手が競技に優勝したことを示す。

選手のスキルを特定したら、! s1 s2 ... sn という形式の行を出力する。ここで $s_k$ は選手 $k$ のスキルと等しくなければならない。

不正なクエリを行ったり、$N$ 回を超える競技を開催しようとした場合、あなたの解は Wrong Answer と判定される。さらに、出力したスキルの集合がインタラクタが想定しているスキルの集合と異なる場合も、Wrong Answer と判定される。いずれの場合も、インタラクションは直ちに終了する。それ以外の場合、スコアリングセクションで説明されるスコアが得られる。

インタラクタは適応的である可能性があることに注意すること。つまり、選手の真のスキルはインタラクションを通じて変化する可能性があるが、現在のスキルの集合は常に過去のすべての競技結果と矛盾しないものとなる。

制約

各テストケースについて、$q$ をあなたが開催した競技の回数とする。また、各 $N$ に対して、$c_N$ をスキルを特定できることを保証するために必要な最小の競技回数とする。

すべてのテストケースで $q \le c_N$ を満たした場合、100点を得る。それ以外の場合、10点を得る。この問題の制約下では、10点を得るためにはすべてのテストケースで $q \le N$ を満たす必要があることに注意すること。

入出力例

入力 1

1
5
3 2 1 0 1
3 1 2 1 0
3 0 1 2 1
3 1 0 1 2

出力 1

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

注記

サンプルにおいて、選手たちのスキルはそれぞれ 4, 2, 1, 5, 3 である。

最初に行われた競技では、選手たちは環状リスト $[1, 2, 3, 4, 5]$ に並べられる。競技は以下のように進行する（各ラウンドにおいて、敗退した選手は $X$ と表記する）。

• ラウンド 1:
  • 3番目の位置の選手（スキル 1 の選手 3）は、2番目と4番目の位置の選手（スキル 2 の選手 2、スキル 5 の選手 4）に負けて敗退する。
  • 5番目の位置の選手（スキル 3 の選手 5）は、4番目と1番目の位置の選手（スキル 5 の選手 4、スキル 4 の選手 1）に負けて敗退する。
  • 1番目の位置の選手（スキル 4 の選手 1）は、5番目と2番目の位置の選手（スキル 3 の選手 5、スキル 2 の選手 2）に勝ち、敗退しない。
  • 2番目の位置の選手（スキル 2 の選手 2）は、3番目の位置の選手（スキル 1 の選手 3）に勝ち、敗退しない。
  • 4番目の位置の選手（スキル 5 の選手 4）は、3番目と5番目の位置の選手（スキル 1 の選手 3、スキル 3 の選手 5）に勝ち、敗退しない。
• ラウンド 2 において、選手リストは $[1, 2, X, 4, X]$ となる。
  • 2番目の位置の選手は、1番目と4番目の位置の選手に負けて敗退する。
  • 1番目の位置の選手は、2番目の位置の選手に勝ち、敗退しない。
  • 4番目の位置の選手は、他の2人の選手に勝ち、敗退しない。
• ラウンド 3 において、選手リストは $[1, X, X, 4, X]$ となる。
  • 1番目の位置の選手は、4番目と4番目の位置の選手（同一人物）に負けて敗退する。
  • 4番目の位置の選手は、1番目の位置の選手に勝ち、敗退しない。

したがって、 1番目の位置の選手はラウンド 3 で敗退した。 2番目の位置の選手はラウンド 2 で敗退した。 3番目の位置の選手はラウンド 1 で敗退した。 4番目の位置の選手は競技に優勝した。 * 5番目の位置の選手はラウンド 1 で敗退した。

これにより、クエリに対する回答は $[3, 2, 1, 0, 1]$ となる。

2回目に行われた競技では、選手たちは環状リスト $[1, 3, 5, 2, 4]$ に並べられる。競技は以下のように進行する。

• ラウンド 1:
  • 2番目の位置の選手（スキル 1 の選手 3）は、1番目と3番目の位置の選手（スキル 4 の選手 1、スキル 3 の選手 5）に負けて敗退する。
  • 4番目の位置の選手（スキル 2 の選手 2）は、3番目と5番目の位置の選手（スキル 3 の選手 5、スキル 5 の選手 4）に負けて敗退する。
  • 1番目の位置の選手（スキル 4 の選手 1）は、2番目の位置の選手（スキル 1 の選手 3）に勝ち、敗退しない。
  • 3番目の位置の選手（スキル 3 の選手 5）は、2番目と4番目の位置の選手（スキル 1 の選手 3、スキル 2 の選手 2）に勝ち、敗退しない。
  • 5番目の位置の選手（スキル 5 の選手 4）は、4番目と1番目の位置の選手（スキル 2 の選手 2、スキル 4 の選手 1）に勝ち、敗退しない。
• ラウンド 2 において、選手リストは $[1, X, 5, X, 4]$ となる。
  • 3番目の位置の選手は、1番目と5番目の位置の選手に負けて敗退する。
  • 1番目の位置の選手は、3番目の位置の選手に勝ち、敗退しない。
  • 5番目の位置の選手は、他の2人の選手に勝ち、敗退しない。
• ラウンド 3 において、選手リストは $[1, X, X, X, 4]$ となる。
  • 1番目の位置の選手は、5番目と5番目の位置の選手（同一人物）に負けて敗退する。
  • 5番目の位置の選手は、1番目の位置の選手に勝ち、敗退しない。

したがって、 1番目の位置の選手はラウンド 3 で敗退した。 2番目の位置の選手はラウンド 1 で敗退した。 3番目の位置の選手はラウンド 2 で敗退した。 4番目の位置の選手はラウンド 1 で敗退した。 * 5番目の位置の選手は競技に優勝した。

これにより、クエリに対する回答は $[3, 1, 2, 1, 0]$ となる。