Dziękuję za twoją ciężką pracę, kochanie. Little Cyan Fish nie wie, ile z jego zaszyfrowanych słów uda się przekazać, ale mimo to dziękuje ci za to, że doszedłeś z Little Cyan Fish aż do tego miejsca. Wydarzyło się tak wiele rzeczy, tak wiele absurdalnych rzeczy; Little Cyan Fish jest zmęczony, bardzo zmęczony... W minionym roku Little Cyan Fish kilkakrotnie czuł, że sam siebie uratuje, ale koniec końców nie był wystarczająco silny, by przeciąć oplatające jego ciało nici. Little Cyan Fish zawsze wyobraża sobie, że w tym odległym miejscu istnieje drugie ja, które wyraźnie widzi mapę jego życia.

— „Longing for the Distance” · Finał 10. Chińskiego Akademickiego Konkursu Programistycznego

To jest zadanie interaktywne.

Cóż, może spróbujesz przekonać się, jak trudne to będzie. Little Cyan Fish czuje, że jego życie jest permutacją o nieznanym kształcie. Ludzie zawsze mówią, że świat jest pełen losowości, ale dlaczego Little Cyan Fish ma zawsze takiego pecha...? Aha! Może losowość po prostu jest aż tak głęboka! Dlatego Little Cyan Fish decyduje, że ta jego permutacja zostanie wygenerowana losowo w następujący sposób:

• Wygeneruj losową permutację $p_1, p_2, \dots, p_n$: wybraną jednostajnie losowo spośród wszystkich $n!$ możliwych permutacji liczb od $1$ do $n$.
• Jeśli $p_1 > p_n$, odwróć całą permutację.

Nie możesz bezpośrednio zaobserwować struktury tej permutacji, ale Little Cyan Fish obdarzył cię supermocą: zadawaniem pytań! Za każdym razem możesz interaktywnie zapytać o wartość odległości między dwiema liczbami w permutacji modulo $3$. Dokładniej, za każdym razem możesz wybrać dwie liczby $u, v$ ($1 \le u, v \le n$, $u \ne v$), a permutacja powie ci, jaka jest odległość między tymi dwiema liczbami modulo $3$ (tzn. znajdując dwa indeksy $i, j$ spełniające $p_i = u, p_j = v$, permutacja odpowie $|i - j| \bmod 3$).

Teraz Little Cyan Fish chce, abyś spróbował zobaczyć, co uda ci się uzyskać. Musisz pomóc Little Cyan Fish wyznaczyć tę permutację w co najwyżej $25n$ zapytaniach.

Wejście

Istnieje wiele przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T \le 1000$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego najpierw musisz wczytać liczbę całkowitą $n$ ($3 \le n \le 10^4$).

Protokół interakcji

Następnie rozpoczyna się interakcja. W każdym przypadku testowym możesz zadać co najwyżej $25n$ zapytań. Aby zadać zapytanie, musisz wypisać pojedynczy wiersz ? u v ($1 \le u, v \le n$, $u \ne v$), opisujący zapytanie. Następnie musisz wczytać wynik ze standardowego wejścia.

Aby podać odpowiedź, musisz wypisać ! p1 p2 ... pn. Twoje wyjście musi spełniać warunek $p_1 < p_n$. Wypisanie odpowiedzi nie wlicza się do limitu $25n$ zapytań. Po wypisaniu odpowiedzi musisz natychmiast wczytać kolejny przypadek testowy lub natychmiast zakończyć działanie programu.

Po wypisaniu zapytania nie zapomnij wypisać znaku nowej linii i opróżnić bufora wyjścia (flush). Aby to zrobić, możesz użyć fflush(stdout) lub cout.flush() w C++, System.out.flush() w Javie, flush(output) w Pascalu oraz stdout.flush() w Pythonie.

Gwarantuje się, że suma $n$ po wszystkich przypadkach testowych nie przekracza $10^4$.

W tym zadaniu gwarantuje się, że interaktor jest nieadaptacyjny (non-adaptive). Oznacza to, że permutacje są ustalane losowo zgodnie z treścią zadania przed rozpoczęciem procesu interakcji. Nie zmieniają się one w zależności od twoich zapytań. Łącznie jest $30$ przypadków testowych (wliczając przykładowy przypadek testowy).

Przykład

Wejście 1

2
3
2
1
1
4
1
1
1
0
2

Wyjście 1

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

Uwaga

Rysunek 1: Little Cyan Fish i <?> w <?>, zdjęcie wykonane 4 marca 2026 r.