Þetta er gagnvirkt verkefni.

VegiCat þekkir fylki $a_1, a_2, \ldots, a_n$, þar sem hvert stak er $0$, $1$ eða $2$. Hann vill ekki segja þér gildin í því, en þú getur spurt hann spurninga. Í hverri fyrirspurn velur þú tvo vísa $i$ og $j$, og VegiCat segir þér hvort $a_i > a_j$.

VegiCat biður þig um að prenta vísana í ekki-minnkandi röð eftir samsvarandi gildum í fylkinu. Það er, finndu umröðun $p_1, p_2, \ldots, p_n$ á $1, 2, \ldots, n$ þannig að

$$a_{p_1} \le a_{p_2} \le \cdots \le a_{p_n}.$$

Þú mátt gera að hámarki $2n - 3$ fyrirspurnir í hverju prófunartilfelli.

Gagnvirki prófarinn er aðlögunarhæfur (adaptive). Þetta þýðir að fylkið er ekki ákveðið fyrir fram. Prófarinn tryggir að alltaf sé til að minnsta kosti eitt fylki með stökum úr $\{0, 1, 2\}$ sem samræmist öllum svörum sem gefin hafa verið hingað til. Lokaumröðunin þín verður að vera gild fyrir hvert einasta fylki sem samræmist öllum svörum.

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 250$), fjölda prófunartilfella. Lýsing á prófunartilfellunum fylgir.

Hvert prófunartilfelli byrjar á heiltölu $n$ ($2 \le n \le 500$), lengd fylkisins.

Summa $n$ yfir öll prófunartilfelli fer ekki yfir $500$.

Samskipti

Til að gera fyrirspurn skaltu prenta línu á eftirfarandi sniði:

? i j

Hér er $1 \le i, j \le n$. Eftir hverja fyrirspurn skaltu lesa eina heiltölu:

• $1$, ef $a_i > a_j$;
• $0$, ef $a_i \le a_j$.

Fyrirspurnir með $i = j$ og endurteknar fyrirspurnir eru leyfðar og teljast með í fjölda fyrirspurna.

Þegar þú hefur ákvarðað röðina skaltu prenta línu á eftirfarandi sniði:

! p_1 p_2 ... p_n

Hver vísir frá $1$ til $n$ verður að koma fyrir nákvæmlega einu sinni. Að prenta svarið telst ekki sem fyrirspurn.

Ef svarið þitt er rétt skaltu halda áfram í næsta prófunartilfelli með því að lesa $n$ þess, eða ljúka keyrslu forritsins ef þetta var síðasta prófunartilfellið. Prófarinn sendir ekki sérstaka staðfestingu á eftir svari.

Eftir að hver fyrirspurn eða svar er prentað skaltu prenta nýja línu og tæma úttaksbiðminnið (flush). Til að tæma úttaksbiðminnið geturðu notað:

• fflush(stdout) eða cout.flush() í C/C++;
• System.out.flush() í Java og Kotlin;
• sys.stdout.flush() í Python.

Ef þú gerir ógilda fyrirspurn, ferð yfir hámarksfjölda fyrirspurna eða prentar rangt svar færðu dóminn Wrong Answer. Úttak sem fylgir ekki tilgreindu sniði fær einnig dóminn Wrong Answer. Í þessum tilvikum hættir prófarinn keyrslu án þess að senda villuboð.

Examples

Input 1

2
3

1

1

2

0

Output 1

? 1 2

? 2 3

! 3 2 1

? 1 2

! 1 2

Note

Í fyrsta prófunartilfellinu skila fyrirspurnirnar ? 1 2 og ? 2 3 báðar $1$, þannig að $a_1 > a_2 > a_3$. Því er $(3, 2, 1)$ rétt svar.

Í öðru prófunartilfellinu skilar fyrirspurnin ? 1 2 gildinu $0$, þannig að $a_1 \le a_2$. Því er $(1, 2)$ rétt svar.