Merci pour ton travail acharné, chéri(e). Little Cyan Fish ne sait pas combien de ses mots codés peuvent être transmis, mais te remercie quand même d'avoir marché jusqu'ici avec Little Cyan Fish. Tant de choses, tant de choses absurdes se sont produites, Little Cyan Fish est fatigué, très fatigué... Au cours de l'année écoulée, Little Cyan Fish a senti à plusieurs reprises qu'il allait se sauver lui-même, mais après tout, il n'était pas assez fort pour couper les fils sur son corps. Little Cyan Fish imagine toujours que dans cet endroit lointain, il existe un autre lui-même capable de voir clairement la carte de sa vie.

— « Longing for the Distance » · Finale du 10e China Collegiate Programming Contest

Ceci est un problème interactif.

Eh bien, peut-être pouvez-vous essayer de voir à quel point cela sera difficile. Little Cyan Fish a l'impression que sa vie est une permutation de forme inconnue. Les gens disent toujours que le monde est plein de hasard, mais pourquoi Little Cyan Fish est-il toujours aussi malchanceux... ? Aha ! Peut-être que le hasard est tout simplement aussi profond ! Ainsi, Little Cyan Fish décide que sa permutation sera générée aléatoirement de la manière suivante :

• Générer une permutation aléatoire $p_1, p_2, \dots, p_n$ : choisie uniformément au hasard parmi toutes les $n!$ permutations possibles de $1$ à $n$.
• Si $p_1 > p_n$, inverser alors toute la permutation.

Vous ne pouvez pas observer directement la structure de la permutation, mais Little Cyan Fish vous a accordé un super-pouvoir : poser des questions ! À chaque fois, vous pouvez demander de manière interactive la valeur de la distance entre deux nombres dans la permutation modulo $3$. Plus précisément, à chaque fois vous pouvez choisir deux nombres $u, v$ ($1 \le u, v \le n$, $u \ne v$), et la permutation vous indiquera la valeur de la distance entre ces deux nombres modulo $3$ (c'est-à-dire, en trouvant deux indices $i, j$ satisfaisant $p_i = u, p_j = v$, la permutation répondra $|i - j| \bmod 3$).

Maintenant, Little Cyan Fish veut que vous essayiez de voir ce que vous pouvez obtenir. Vous devez aider Little Cyan Fish à déterminer cette permutation en au plus $25n$ requêtes.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un seul entier $T$ ($1 \le T \le 1000$), indiquant le nombre de cas de test.

Pour chaque cas de test, vous devez d'abord lire un entier $n$ ($3 \le n \le 10^4$).

Protocole d'interaction

Ensuite, l'interaction commence. Vous ne pouvez faire plus de $25n$ requêtes dans chaque cas de test. Pour faire une requête, vous devez afficher une seule ligne ? u v ($1 \le u, v \le n$, $u \ne v$), décrivant une requête. Ensuite, vous devez lire le résultat depuis l'entrée standard.

Pour fournir votre réponse, vous devez afficher ! p1 p2 ... pn. Votre sortie doit satisfaire $p_1 < p_n$. L'affichage de la réponse ne sera pas compté dans la limite des $25n$ requêtes. Après avoir affiché la réponse, vous devez lire immédiatement le cas de test suivant, ou quitter immédiatement votre programme.

Après avoir affiché une requête, n'oubliez pas d'afficher un caractère de retour à la ligne et de vider le tampon de sortie (flush). Pour ce faire, vous pouvez utiliser fflush(stdout) ou cout.flush() en C++, System.out.flush() en Java, flush(output) en Pascal et stdout.flush() en Python.

Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $10^4$.

Dans ce problème, il est garanti que l'interacteur est non adaptatif. C'est-à-dire que les permutations sont déterminées aléatoirement comme indiqué dans l'énoncé avant le processus d'interaction. Elles ne changeront pas en fonction de vos requêtes. Il y a un total de $30$ cas de test (y compris le cas de test d'exemple).

Exemple

Entrée 1

2
3
2
1
1
4
1
1
1
0
2

Sortie 1

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

Note

Figure 1 : Little Cyan Fish & <?> à <?> prise le 4 mars 2026