Takk for det harde arbeidet ditt, kjære. Little Cyan Fish vet ikke hvor mye av kodeordene hans som kan formidles, men takker deg likevel for at du har gått helt til dette punktet sammen med Little Cyan Fish. Så mange ting, så mange absurde ting har skjedd, Little Cyan Fish er sliten, veldig sliten... I løpet av det siste året følte Little Cyan Fish flere ganger at han kom til å redde seg selv, men når alt kom til alt, var han ikke sterk nok til å kutte trådene på kroppen sin. Little Cyan Fish ser alltid for seg at på det fjerne stedet finnes det et annet jeg som tydelig kan se kartet over livet hans.

— «Longing for the Distance» · Finalen i 10th China Collegiate Programming Contest

Dette er et interaktivt problem.

Vel, kanskje du kan prøve og se hvor vanskelig dette vil bli. Little Cyan Fish føler at livet hans er en permutasjon av ukjent form. Folk sier alltid at verden er full av tilfeldigheter, men hvorfor er Little Cyan Fish alltid så uheldig...? Aha! Kanskje tilfeldighetene rett og slett er så dype! Så Little Cyan Fish bestemmer at denne permutasjonen hans skal genereres tilfeldig på følgende måte:

• Generer en tilfeldig permutasjon $p_1, p_2, \dots, p_n$: valgt uniformt tilfeldig blant alle de $n!$ mulige permutasjonene av $1$ til $n$.
• Hvis $p_1 > p_n$, snu hele permutasjonen.

Du kan ikke observere strukturen til permutasjonen direkte, men Little Cyan Fish har gitt deg en superkraft: å spørre! Hver gang kan du interaktivt spørre om verdien av avstanden mellom to tall i permutasjonen modulo $3$. Mer spesifikt kan du hver gang velge to tall $u, v$ ($1 \le u, v \le n$, $u \ne v$), og permutasjonen vil fortelle deg verdien av avstanden mellom disse to tallene modulo $3$ (det vil si, ved å finne to indekser $i, j$ som tilfredsstiller $p_i = u, p_j = v$, vil permutasjonen svare $|i - j| \bmod 3$).

Nå vil Little Cyan Fish at du skal prøve og se hva du kan få til. Du må hjelpe Little Cyan Fish med å bestemme denne permutasjonen med ikke mer enn $25n$ spørringer.

Inndata

Det er flere testtilfeller. Den første linjen av inndataene inneholder et enkelt heltall $T$ ($1 \le T \le 1000$), som angir antallet testtilfeller.

For hvert testtilfelle må du først lese inn et heltall $n$ ($3 \le n \le 10^4$).

Interaksjonsprotokoll

Deretter begynner interaksjonen. Du kan gjøre høyst $25n$ spørringer i hvert testtilfelle. For å gjøre en spørring må du skrive ut én enkelt linje ? u v ($1 \le u, v \le n$, $u \ne v$), som beskriver en spørring. Deretter må du lese resultatet fra standard inndata.

For å oppgi svaret ditt må du skrive ut ! p1 p2 ... pn. Utdataene dine må tilfredsstille $p_1 < p_n$. Å skrive ut svaret teller ikke mot grensen på $25n$ spørringer. Etter at du har skrevet ut svaret, må du umiddelbart lese inn neste testtilfelle, eller avslutte programmet ditt umiddelbart.

Etter å ha skrevet ut en spørring, ikke glem å skrive ut et linjeskifttegn og tømme utdatastrømmen (flush). For å gjøre dette kan du bruke fflush(stdout) eller cout.flush() i C++, System.out.flush() i Java, flush(output) i Pascal og stdout.flush() i Python.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $10^4$.

I dette problemet er det garantert at interaktoren er ikke-adaptiv. Det vil si at permutasjonene bestemmes tilfeldig slik problemet beskriver før interaksjonsprosessen. De vil ikke endre seg etter spørringene dine. Det er totalt $30$ testtilfeller (inkludert eksempeltesttilfellet).

Eksempel

Inndata 1

2
3
2
1
1
4
1
1
1
0
2

Utdata 1

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

Merk

Figur 1: Little Cyan Fish & <?> ved <?> tatt 4. mars 2026