Tack för ditt hårda arbete, älskling. Little Cyan Fish vet inte hur mycket av hans kodord som kan förmedlas, men tackar dig ändå för att du har vandrat ända hit med Little Cyan Fish. Så många saker, så många absurda saker har hänt, Little Cyan Fish är trött, väldigt trött... Under det senaste året kände Little Cyan Fish flera gånger att han var på väg att rädda sig själv, men när allt kommer omkring var han inte tillräckligt stark för att klippa av trådarna på sin kropp. Little Cyan Fish föreställer sig alltid att det på den där avlägsna platsen finns ett annat jag som tydligt kan se kartan över hans liv.

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

Detta är ett interaktivt problem.

Nåväl, du kan kanske prova och se hur svårt det här blir. Little Cyan Fish känner att hans liv är en permutation av okänd form. Folk säger alltid att världen är full av slumpmässighet, men varför har Little Cyan Fish alltid sådan otur...? Aha! Kanske är slumpmässigheten helt enkelt så här djupgående! Så Little Cyan Fish bestämmer att denna hans permutation ska genereras slumpmässigt på följande sätt:

• Generera en slumpmässig permutation $p_1, p_2, \dots, p_n$: vald likformigt slumpmässigt bland alla $n!$ möjliga permutationer av $1$ till $n$.
• Om $p_1 > p_n$, vänd då på hela permutationen.

Du kan inte direkt observera permutationens struktur, men Little Cyan Fish har gett dig en superkraft: att fråga! Varje gång kan du interaktivt fråga efter värdet på avståndet mellan två tal i permutationen modulo $3$. Mer specifikt kan du varje gång välja två tal $u, v$ ($1 \le u, v \le n$, $u \ne v$), och permutationen kommer att berätta värdet på avståndet mellan dessa två tal modulo $3$ (det vill säga, genom att hitta två index $i, j$ som uppfyller $p_i = u, p_j = v$ svarar permutationen $|i - j| \bmod 3$).

Nu vill Little Cyan Fish att du ska försöka och se vad du kan få fram. Du måste hjälpa Little Cyan Fish att bestämma denna permutation med högst $25n$ frågor.

Indata

Det finns flera testfall. Den första raden i indata innehåller ett enda heltal $T$ ($1 \le T \le 1000$), som anger antalet testfall.

För varje testfall måste du först läsa in ett heltal $n$ ($3 \le n \le 10^4$).

Interaktionsprotokoll

Därefter börjar interaktionen. Du kan ställa högst $25n$ frågor i varje testfall. För att ställa en fråga måste du skriva ut en enda rad ? u v ($1 \le u, v \le n$, $u \ne v$), som beskriver en fråga. Sedan måste du läsa in resultatet från standardindata.

För att ange ditt svar måste du skriva ut ! p1 p2 ... pn. Din utdata måste uppfylla $p_1 < p_n$. Att skriva ut svaret räknas inte mot gränsen på $25n$ frågor. Efter att du har skrivit ut svaret måste du omedelbart läsa in nästa testfall, eller omedelbart avsluta ditt program.

Efter att ha skrivit ut en fråga, glöm inte att skriva ut ett radbrytningstecken och tömma utdataströmmen (flush). För att göra detta kan du använda fflush(stdout) eller cout.flush() i C++, System.out.flush() i Java, flush(output) i Pascal och stdout.flush() i Python.

Det garanteras att summan av $n$ över alla testfall inte överstiger $10^4$.

I detta problem garanteras det att interaktorn är icke-adaptiv. Det vill säga, permutationerna bestäms slumpmässigt såsom angivits i problemet före interaktionsprocessen. De kommer inte att ändras beroende på dina frågor. Det finns totalt $30$ testfall (inklusive exempeltestfallet).

Exempel

Indata 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

Förklaring

Figur 1: Little Cyan Fish & <?> vid <?> tagen den 4 mars 2026