Это задача интерактивная.

Море, мы снова встретились. Пусть и следующие летние каникулы будут счастливыми! Очень давно Уна и Камоэ уже были хорошими друзьями.

Они любили играть в игры. В прошлый раз игра, придуманная Уной, была легко решена отличной стратегией Камоэ. На этот раз Уна принесла новую игру.

Уна рассматривает дерево с $n$ вершинами. Камоэ может сделать не более $n$ запросов:

• Камоэ может сообщить Уне перестановку $P_1, P_2, \dots, P_n$ (где $0 \le P_i \le n-1$ и все $P_i$ различны). Тогда Уна сообщает Камоэ длину взвешенного диаметра дерева, когда каждой вершине $i$ присвоен вес $2^{P_i}$.

Но иногда Камоэ замечает, что Уна устраивает неприятности. Точнее, бывают случаи, когда невозможно однозначно определить дерево, сколько бы запросов ни задавать. В таких случаях Камоэ может сообщить, что решения нет.

Протокол взаимодействия

Это задача интерактивная. После каждого вывода обязательно сбрасывайте буфер вывода. Для этого можно использовать:

• C/C++: fflush(stdout) или cout.flush()
• Java и Kotlin: System.out.flush()
• Python: sys.stdout.flush()

Сначала считайте количество тестовых случаев $T$ ($1 < T < 10^4$). Для каждого тестового случая считайте размер дерева $n$ ($2 \le n \le 100$, $\sum n^2 < 10^6$).

Чтобы сделать запрос, выведите одну строку в формате "? $P_1 P_2 \dots P_n$" (где $0 \le P_i \le n-1$ и $P_i \ne P_j$ для $1 < i < j \le n$). Затем считайте строку из $n$ символов, представляющую вес диаметра дерева в двоичной записи. Если запрос недействителен или вы сделали более $n$ запросов в одном тестовом случае, программа жюри выведет -1. Прочитав -1, вы должны немедленно завершить работу, чтобы избежать неопределённого поведения.

Если вы считаете, что невозможно однозначно определить дерево, выведите "! NO". Иначе выведите одну строку в формате "! YES $u_1 v_1 u_2 v_2 \dots u_{n-1} v_{n-1}$", где $(u_i, v_i)$ — рёбра дерева. Рёбра можно выводить в любом порядке.

После этого считайте слово "OK" или "WA", указывающее на правильность ответа. Если вы прочитали "WA", вы должны немедленно завершить работу, чтобы избежать неопределённого поведения. Если вы вывели YES, хотя дерево невозможно определить, даже если ответ был верен, Уна решит, что вы жульничаете, и ответ будет считаться неверным.

Программа жюри не является адаптивной, поэтому ответ не меняется после запросов.

Примеры

Входные данные 1

2
4
1110
1110
OK
3
111
OK

Выходные данные 1

? 0 1 2 3
? 2 1 0 3
! YES 1 4 2 4 3 4
? 0 1 2
! NO

Примечание

Предоставляется инструмент тестирования, который участники могут использовать для разработки и тестирования своего решения. Этот инструмент можно скачать из приложенных файлов. Запустите инструмент с опцией "-h", чтобы получить описание использования. Инструмент тестирования реализует лишь часть функций реальной программы жюри и поддерживает только некоторые сценарии тестирования.