Dette er en interaktiv oppgave.

VegiCat kjenner en tabell $a_1, a_2, \ldots, a_n$, der hvert element er $0$, $1$ eller $2$. Han vil ikke fortelle deg verdiene, men du kan stille ham spørsmål. I hver spørring velger du to indekser $i$ og $j$, og VegiCat forteller deg om $a_i > a_j$.

VegiCat ber deg om å skrive ut indeksene i ikke-avtakende rekkefølge etter de tilhørende tabellverdiene. Det vil si, finn en permutasjon $p_1, p_2, \ldots, p_n$ av $1, 2, \ldots, n$ slik at

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

Du kan gjøre høyst $2n - 3$ spørringer i hvert testtilfelle.

Interaktoren er adaptiv. Dette betyr at tabellen ikke er fastsatt på forhånd. Interaktoren garanterer at det alltid finnes minst én tabell med elementer i $\{0, 1, 2\}$ som er konsistent med alle svarene som er gitt så langt. Din endelige permutasjon må være gyldig for enhver tabell som er konsistent med alle svarene.

Inndata

Den første linjen inneholder et heltall $T$ ($1 \le T \le 250$), antallet testtilfeller. Beskrivelsen av testtilfellene følger.

Hvert testtilfelle begynner med et heltall $n$ ($2 \le n \le 500$), lengden på tabellen.

Summen av $n$ over alle testtilfeller overstiger ikke $500$.

Interaksjon

For å gjøre en spørring, skriv ut én linje på følgende format:

? i j

Her er $1 \le i, j \le n$. Etter hver spørring skal du lese inn ett heltall:

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

Spørringer med $i = j$ og gjentatte spørringer er tillatt og teller med i antall spørringer.

Når du har bestemt rekkefølgen, skriv ut én linje på følgende format:

! p_1 p_2 ... p_n

Hver indeks fra $1$ til $n$ må forekomme nøyaktig én gang. Å skrive ut svaret teller ikke som en spørring.

Hvis svaret ditt er riktig, går du videre til neste testtilfelle ved å lese inn dets $n$, eller avslutter programmet hvis dette var det siste testtilfellet. Interaktoren sender ingen egen bekreftelse etter et svar.

Etter å ha skrevet ut hver spørring eller hvert svar, må du skrive ut et linjeskift og tømme utdatabufferen (flush). For å tømme utdatabufferen kan du bruke:

• fflush(stdout) eller cout.flush() i C/C++;
• System.out.flush() i Java og Kotlin;
• sys.stdout.flush() i Python.

Hvis du gjør en ugyldig spørring, overskrider spørregrensen eller skriver ut feil svar, vil du få bedømmelsen Wrong Answer. Utdata som ikke følger det angitte formatet, blir også bedømt som Wrong Answer. I disse tilfellene avslutter interaktoren uten å sende en feilmelding.

Examples

Input 1

2
3

1

1

2

0

Output 1

? 1 2

? 2 3

! 3 2 1

? 1 2

! 1 2

Note

I det første testtilfellet returnerer spørringene ? 1 2 og ? 2 3 begge $1$, så $a_1 > a_2 > a_3$. Derfor er $(3, 2, 1)$ et riktig svar.

I det andre testtilfellet returnerer spørringen ? 1 2 verdien $0$, så $a_1 \le a_2$. Derfor er $(1, 2)$ et riktig svar.