Istnieje $N$ kolarzy $1, \dots, N$. Każdy kolarz ma unikalne umiejętności od $1$ do $N$, a gdy dwóch kolarzy staje naprzeciw siebie, zawsze wygrywa ten z wyższymi umiejętnościami.

Kolarze lubią brać udział w zawodach. W zawodach kolarze są ustawieni w cyklicznej liście. Zawody odbywają się w rundach. W każdej rundzie kolarz ściga się z każdym ze swoich sąsiadów. Jeśli przegra z obydwoma, zostaje wyeliminowany.

Nie znasz umiejętności kolarzy i chciałbyś je poznać. Możesz organizować zawody wszystkich kolarzy, za każdym razem wybierając ich ustawienie na liście cyklicznej, i otrzymasz informację, w której rundzie każdy kolarz został wyeliminowany.

Określ umiejętności kolarzy, używając optymalnej liczby zawodów lub używając $N$ zawodów, aby uzyskać częściową liczbę punktów.

Interakcja

Każdy test zawiera wiele przypadków testowych. Interakcja rozpoczyna się od wiersza zawierającego pojedynczą liczbę całkowitą $T$ ($1 \le T \le 10^4$), liczbę przypadków testowych.

Każdy przypadek testowy rozpoczyna się od wiersza zawierającego pojedynczą liczbę całkowitą $N$ ($3 \le N \le 300$), liczbę kolarzy.

Następnie możesz organizować zawody. Aby przeprowadzić zawody, wypisz wiersz "? $a_1$ $a_2$ $\dots$ $a_n$" — $a_k$ oznacza, że kolarz $a_k$ znajduje się na $k$-tym miejscu listy kolarzy. Lista $a_1, \dots, a_n$ musi być permutacją $1, \dots, n$.

Odpowiedzią na Twoje zapytanie będzie wiersz "$r_1$ $r_2$ $\dots$ $r_n$" — $r_k$ spełnia $0 \le r_k < n$. Gdy $r_k > 0$, oznacza to, że kolarz na $k$-tym miejscu został wyeliminowany w rundzie $r_k$ zawodów. Jeśli $r_k = 0$, oznacza to, że dany kolarz wygrał zawody.

Gdy określisz umiejętności kolarzy, wypisz wiersz "! $s_1$ $s_2$ $\dots$ $s_n$" — $s_k$ powinno być równe umiejętności kolarza $k$.

Jeśli wykonasz nieprawidłowe zapytanie lub spróbujesz przeprowadzić więcej niż $N$ zawodów, Twoje rozwiązanie otrzyma werdykt Wrong Answer. Dodatkowo, jeśli zbiór umiejętności, który wypiszesz, różni się od zbioru umiejętności, który ma interaktor, Twoje rozwiązanie otrzyma werdykt Wrong Answer. W obu przypadkach interakcja zostanie natychmiast przerwana. W przeciwnym razie otrzymasz punkty zgodnie z sekcją punktacji.

Zauważ, że interaktor może być adaptacyjny: prawdziwe umiejętności kolarzy mogą zmieniać się w trakcie interakcji, ale bieżący zbiór umiejętności będzie zawsze spójny ze wszystkimi poprzednimi zawodami.

Punktacja

Dla każdego przypadku testowego niech $q$ będzie liczbą zawodów przeprowadzonych przez Twoje rozwiązanie. Dodatkowo, dla każdego $N$, niech $c_N$ będzie minimalną liczbą zawodów niezbędną do zagwarantowania możliwości określenia umiejętności.

Otrzymasz 100 punktów, jeśli $q \le c_N$ dla wszystkich przypadków testowych. W przeciwnym razie otrzymasz 10 punktów. Zauważ, że przy ograniczeniach problemu, otrzymanie 10 punktów wymaga spełnienia $q \le N$ dla wszystkich przypadków testowych.

Przykład

Wejście 1

1
5
Fixed
4 2 1 5 3

Wyjście 1

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

Uwagi

W przykładzie umiejętności kolarzy wynoszą odpowiednio 4, 2, 1, 5, 3.

W pierwszych przeprowadzonych zawodach kolarze są ustawieni na liście cyklicznej $[1, 2, 3, 4, 5]$. Zawody przebiegają następująco; w każdej rundzie lista kolarzy jest pokazana z wyeliminowanymi kolarzami zastąpionymi przez $X$.

• W rundzie 1:
  • Kolarz na miejscu 3 (kolarz 3 o umiejętności 1) przegrywa z kolarzami na miejscach 2 i 4 (kolarze 2, 4 o umiejętnościach 2, 5) i zostaje wyeliminowany.
  • Kolarz na miejscu 5 (kolarz 5 o umiejętności 3) przegrywa z kolarzami na miejscach 4 i 1 (kolarze 4, 1 o umiejętnościach 5, 4) i zostaje wyeliminowany.
  • Kolarz na miejscu 1 (kolarz 1 o umiejętności 4) wygrywa z kolarzami na miejscach 5, 2 (kolarze 5, 2 o umiejętnościach 3, 2) i dlatego nie zostaje wyeliminowany.
  • Kolarz na miejscu 2 (kolarz 2 o umiejętności 2) wygrywa z kolarzem na miejscu 3 (kolarz 3 o umiejętności 1) i dlatego nie zostaje wyeliminowany.
  • Kolarz na miejscu 4 (kolarz 4 o umiejętności 5) wygrywa z kolarzami na miejscach 3, 5 (kolarze 3, 5 o umiejętnościach 1, 3) i dlatego nie zostaje wyeliminowany.
• W rundzie 2 lista kolarzy to $[1, 2, X, 4, X]$.
  • Kolarz na miejscu 2 przegrywa z kolarzami na miejscach 1 i 4 i zostaje wyeliminowany.
  • Kolarz na miejscu 1 wygrywa z kolarzem na miejscu 2 i dlatego nie zostaje wyeliminowany.
  • Kolarz na miejscu 4 wygrywa z pozostałymi dwoma kolarzami i dlatego nie zostaje wyeliminowany.
• W rundzie 3 lista kolarzy to $[1, X, X, 4, X]$.
  • Kolarz na miejscu 1 przegrywa z kolarzami na miejscach 4 i 4 (którzy są tym samym kolarzem) i zostaje wyeliminowany.
  • Kolarz na miejscu 4 wygrywa z kolarzem na miejscu 1 i dlatego nie zostaje wyeliminowany.

Dlatego: Kolarz na miejscu 1 został wyeliminowany w rundzie 3. Kolarz na miejscu 2 został wyeliminowany w rundzie 2. Kolarz na miejscu 3 został wyeliminowany w rundzie 1. Kolarz na miejscu 4 wygrał zawody. * Kolarz na miejscu 5 został wyeliminowany w rundzie 1.

co daje odpowiedź na zapytanie $[3, 2, 1, 0, 1]$.

W drugich przeprowadzonych zawodach kolarze są ustawieni na liście cyklicznej $[1, 3, 5, 2, 4]$. Zawody przebiegają następująco:

• W rundzie 1:
  • Kolarz na miejscu 2 (kolarz 3 o umiejętności 1) przegrywa z kolarzami na miejscach 1 i 3 (kolarze 1, 5 o umiejętnościach 4, 3) i zostaje wyeliminowany.
  • Kolarz na miejscu 4 (kolarz 2 o umiejętności 2) przegrywa z kolarzami na miejscach 3 i 5 (kolarze 5, 4 o umiejętnościach 3, 5) i zostaje wyeliminowany.
  • Kolarz na miejscu 1 (kolarz 1 o umiejętności 4) wygrywa z kolarzem na miejscu 2 (kolarz 3 o umiejętności 1) i dlatego nie zostaje wyeliminowany.
  • Kolarz na miejscu 3 (kolarz 5 o umiejętności 3) wygrywa z kolarzami na miejscach 2, 4 (kolarze 3, 2 o umiejętnościach 1, 2) i dlatego nie zostaje wyeliminowany.
  • Kolarz na miejscu 5 (kolarz 4 o umiejętności 5) wygrywa z kolarzami na miejscach 4, 1 (kolarze 2, 1 o umiejętnościach 2, 4) i dlatego nie zostaje wyeliminowany.
• W rundzie 2 lista kolarzy to $[1, X, 5, X, 4]$.
  • Kolarz na miejscu 3 przegrywa z kolarzami na miejscach 1 i 5 i zostaje wyeliminowany.
  • Kolarz na miejscu 1 wygrywa z kolarzem na miejscu 3 i dlatego nie zostaje wyeliminowany.
  • Kolarz na miejscu 5 wygrywa z pozostałymi dwoma kolarzami i dlatego nie zostaje wyeliminowany.
• W rundzie 3 lista kolarzy to $[1, X, X, X, 4]$.
  • Kolarz na miejscu 1 przegrywa z kolarzami na miejscach 5 i 5 (którzy są tym samym kolarzem) i zostaje wyeliminowany.
  • Kolarz na miejscu 5 wygrywa z kolarzem na miejscu 1 i dlatego nie zostaje wyeliminowany.

Dlatego: Kolarz na miejscu 1 został wyeliminowany w rundzie 3. Kolarz na miejscu 2 został wyeliminowany w rundzie 1. Kolarz na miejscu 3 został wyeliminowany w rundzie 2. Kolarz na miejscu 4 został wyeliminowany w rundzie 1. * Kolarz na miejscu 5 wygrał zawody.

co daje odpowiedź na zapytanie $[3, 1, 2, 1, 0]$.