Це інтерактивна задача.
VegiCat знає масив $a_1, a_2, \ldots, a_n$, кожен елемент якого дорівнює $0$, $1$ або $2$. Він не хоче повідомляти вам його значення, але ви можете ставити йому запитання. У кожному запиті ви обираєте два індекси $i$ та $j$, а VegiCat повідомляє вам, чи виконується $a_i > a_j$.
VegiCat просить вас вивести індекси в порядку неспадання відповідних значень масиву. Тобто знайдіть таку перестановку $p_1, p_2, \ldots, p_n$ чисел $1, 2, \ldots, n$, що
$$a_{p_1} \le a_{p_2} \le \cdots \le a_{p_n}.$$
У кожному наборі вхідних даних ви можете зробити щонайбільше $2n - 3$ запитів.
Інтерактор є адаптивним. Це означає, що масив не зафіксований заздалегідь. Інтерактор гарантує, що завжди існує принаймні один масив з елементами з $\{0, 1, 2\}$, узгоджений з усіма наданими досі відповідями. Ваша підсумкова перестановка має бути коректною для кожного масиву, узгодженого з усіма відповідями.
Вхідні дані
Перший рядок містить ціле число $T$ ($1 \le T \le 250$) — кількість наборів вхідних даних. Далі йде опис наборів вхідних даних.
Кожен набір вхідних даних починається з цілого числа $n$ ($2 \le n \le 500$) — довжини масиву.
Сума $n$ за всіма наборами вхідних даних не перевищує $500$.
Взаємодія
Щоб зробити запит, виведіть рядок у такому форматі:
? i j
Тут $1 \le i, j \le n$. Після кожного запиту зчитайте одне ціле число:
- $1$, якщо $a_i > a_j$;
- $0$, якщо $a_i \le a_j$.
Запити з $i = j$ та повторні запити дозволені й враховуються в загальній кількості запитів.
Коли ви визначите порядок, виведіть рядок у такому форматі:
! p_1 p_2 ... p_n
Кожен індекс від $1$ до $n$ повинен зустрітися рівно один раз. Виведення відповіді не вважається запитом.
Якщо ваша відповідь правильна, переходьте до наступного набору вхідних даних, зчитавши його $n$, або завершіть роботу програми, якщо це був останній набір вхідних даних. Інтерактор не надсилає окремого підтвердження після відповіді.
Після виведення кожного запиту або відповіді виведіть символ нового рядка та очистьте буфер виведення (flush). Для очищення буфера виведення ви можете використати:
fflush(stdout)абоcout.flush()у C/C++;System.out.flush()у Java та Kotlin;sys.stdout.flush()у Python.
Якщо ви зробите некоректний запит, перевищите ліміт запитів або виведете неправильну відповідь, ви отримаєте вердикт Wrong Answer. Виведення, що не відповідає вказаному формату, також оцінюється як Wrong Answer. У цих випадках інтерактор завершує роботу без надсилання повідомлення про помилку.
Examples
Input 1
2 3 1 1 2 0
Output 1
? 1 2 ? 2 3 ! 3 2 1 ? 1 2 ! 1 2
Note
У першому наборі вхідних даних запити ? 1 2 та ? 2 3 обидва повертають $1$, тому $a_1 > a_2 > a_3$. Отже, $(3, 2, 1)$ є правильною відповіддю.
У другому наборі вхідних даних запит ? 1 2 повертає $0$, тому $a_1 \le a_2$. Отже, $(1, 2)$ є правильною відповіддю.