Це інтерактивна задача. Не забувайте очищувати буфер виводу після кожного друку. Для цього можна використовувати:

• fflush(stdout) або cout.flush() у C/C++;
• System.out.flush() у Java та Kotlin;
• sys.stdout.flush() у Python;
• Для інших мов зверніться до документації.

Little Cyan Fish має таємну перестановку $p_0,p_1,\ldots,p_n$ довжини $n+1$, що складається з цілих чисел від $0$ до $n$. Він хоче, щоб ви вгадали цю перестановку. Для цього Little Cyan Fish дозволяє виконати не більше $1024$ запитів такого вигляду:

• ? i j: Отримати індекс $k$ ($0\le k\le n$), для якого $p_k=|p_i-p_j|$.

Звісно, для коректного запиту потрібно гарантувати, що $i$ та $j$ — два цілі числа з $[0,n]$. Наприклад, якщо $p_0=2,p_1=0,p_2=1$, запит ? 0 2 поверне індекс $2$, оскільки $|p_0-p_2|=|2-1|=1=p_2$.

Little Cyan Fish хоче, щоб ви придумали стратегію пошуку перестановки. Звісно, він не хоче, щоб ви виграли надто легко. Тому він адаптивно змінюватиме перестановку $p$, щоб заманити вас у пастку (докладніше див. «Взаємодія»).

Вхідні дані

Є декілька наборів вхідних даних. Перший рядок вводу містить одне ціле число $T$ ($1\le T\le100$), що позначає кількість наборів.

Для кожного набору перший рядок вводу містить одне ціле число $n$ ($1\le n\le1000$). Після цього починається взаємодія.

Взаємодія

Щоб зробити запит, виведіть рядок у такому форматі:

$$?\ i\ j$$

Тут $i$ та $j$ — два цілі числа від $0$ до $n$. Ви повинні гарантувати, що кількість запитів не перевищує $1024$. У відповідь ви отримаєте ціле число $k$, для якого $p_k=|p_i-p_j|$.

Щоб повідомити відповідь, виведіть рядок у такому форматі:

$$!\ p_0\ p_1\ \ldots\ p_n$$

Тут $p$ — перестановка, яку ви бажаєте повідомити.

Після виведення запиту або відповіді не забудьте вивести символ нового рядка й очистити потік виводу.

У цій задачі інтерактор адаптивний. Це означає, що перестановка $p$ може змінюватися залежно від ваших запитів, доки вона не суперечить попереднім запитам.

Приклади

Приклад взаємодії 1

Читання:

1
3

Запис:

? 2 2

Читання:

1

Запис:

? 0 3

Читання:

3

Запис:

! 2 0 3 1

Інструмент тестування: Надано інструмент, що допомагає учасникам розробляти та тестувати розв'язки. Його можна завантажити з вкладень. Запуск із параметром -h має показати опис використання. Інструмент реалізує лише деякі тестові сценарії та частину функцій справжньої програми оцінювання.