Ceci est un problème interactif.

VegiCat connaît un tableau $a_1, a_2, \ldots, a_n$, dont chaque élément vaut $0$, $1$ ou $2$. Il ne souhaite pas vous révéler ses valeurs, mais vous pouvez lui poser des questions. À chaque requête, vous choisissez deux indices $i$ et $j$, et VegiCat vous indique si $a_i > a_j$.

VegiCat vous demande d'afficher les indices par ordre croissant (au sens large) des valeurs correspondantes du tableau. Autrement dit, trouvez une permutation $p_1, p_2, \ldots, p_n$ de $1, 2, \ldots, n$ telle que

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

Vous pouvez effectuer au plus $2n - 3$ requêtes pour chaque cas de test.

L'interacteur est adaptatif. Cela signifie que le tableau n'est pas fixé à l'avance. L'interacteur garantit qu'il existe toujours au moins un tableau dont les éléments appartiennent à $\{0, 1, 2\}$ qui soit cohérent avec toutes les réponses données jusque-là. Votre permutation finale doit être valide pour tout tableau cohérent avec l'ensemble des réponses.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 250$), le nombre de cas de test. La description des cas de test suit.

Chaque cas de test commence par un entier $n$ ($2 \le n \le 500$), la longueur du tableau.

La somme de $n$ sur l'ensemble des cas de test ne dépasse pas $500$.

Interaction

Pour effectuer une requête, affichez une ligne au format suivant :

? i j

Ici, $1 \le i, j \le n$. Après chaque requête, lisez un entier :

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

Les requêtes avec $i = j$ ainsi que les requêtes répétées sont autorisées et comptent dans le nombre total de requêtes.

Lorsque vous avez déterminé l'ordre, affichez une ligne au format suivant :

! p_1 p_2 ... p_n

Chaque indice de $1$ à $n$ doit apparaître exactement une fois. L'affichage de la réponse ne compte pas comme une requête.

Si votre réponse est correcte, passez au cas de test suivant en lisant son entier $n$, ou terminez votre programme s'il s'agissait du dernier cas de test. L'interacteur n'envoie pas de confirmation séparée après une réponse.

Après avoir affiché chaque requête ou réponse, affichez un saut de ligne et videz le tampon de sortie (flush). Pour vider votre tampon de sortie, vous pouvez utiliser :

• fflush(stdout) ou cout.flush() en C/C++ ;
• System.out.flush() en Java et Kotlin ;
• sys.stdout.flush() en Python.

Si vous effectuez une requête invalide, dépassez la limite de requêtes ou affichez une réponse incorrecte, vous recevrez le verdict Wrong Answer. Toute sortie ne respectant pas le format spécifié est également jugée Wrong Answer. Dans ces cas, l'interacteur s'arrête sans envoyer de message d'erreur.

Exemples

Entrée 1

2
3

1

1

2

0

Sortie 1

? 1 2

? 2 3

! 3 2 1

? 1 2

! 1 2

Remarque

Dans le premier cas de test, les requêtes ? 1 2 et ? 2 3 renvoient toutes deux $1$, donc $a_1 > a_2 > a_3$. Par conséquent, $(3, 2, 1)$ est une réponse correcte.

Dans le second cas de test, la requête ? 1 2 renvoie $0$, donc $a_1 \le a_2$. Par conséquent, $(1, 2)$ est une réponse correcte.