В соревновании участвуют $N$ велосипедистов $1, \dots, N$. Каждый велосипедист обладает уникальным уровнем мастерства от $1$ до $N$, и при встрече двух велосипедистов всегда побеждает тот, у кого уровень мастерства выше.

Велосипедисты любят участвовать в соревнованиях. В соревновании велосипедисты выстраиваются в циклический список. Затем соревнование проходит по раундам. В каждом раунде велосипедист соревнуется с каждым из своих соседей. Если он проигрывает обоим, он выбывает.

Вы не знаете уровней мастерства велосипедистов и хотите их определить. Вы можете проводить соревнования среди всех велосипедистов, каждый раз выбирая их порядок в циклическом списке, и получать информацию о том, в каком раунде выбыл каждый велосипедист.

Определите уровни мастерства, используя оптимальное количество соревнований, или используйте $N$ соревнований для получения части баллов.

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

Каждый тест содержит несколько наборов входных данных. Взаимодействие начинается со строки, содержащей единственное целое число $T$ ($1 \le T \le 10^4$), количество наборов входных данных.

Каждый набор входных данных начинается со строки, содержащей единственное целое число $N$ ($3 \le N \le 300$), количество велосипедистов.

Далее вы можете проводить соревнования. Чтобы провести соревнование, выведите строку «? $a_1$ $a_2$ $\dots$ $a_n$», где $a_k$ означает, что велосипедист $a_k$ находится на $k$-й позиции в списке. Список $a_1, \dots, a_n$ должен быть перестановкой чисел $1, \dots, n$.

Ответом на ваш запрос будет строка «$r_1$ $r_2$ $\dots$ $r_n$», где $r_k$ удовлетворяет условию $0 \le r_k < n$. Если $r_k > 0$, это означает, что велосипедист на $k$-й позиции выбыл в раунде $r_k$ соревнования. Если $r_k = 0$, то этот велосипедист выиграл соревнование.

Как только вы определили уровни мастерства велосипедистов, выведите строку «! $s_1$ $s_2$ $\dots$ $s_n$», где $s_k$ должно быть равно уровню мастерства велосипедиста $k$.

Если вы сделаете некорректный запрос или попытаетесь провести более $N$ соревнований, ваше решение получит вердикт Wrong Answer. Кроме того, если набор уровней мастерства, который вы вывели, отличается от набора, задуманного интерактором, ваше решение получит вердикт Wrong Answer. В обоих случаях взаимодействие немедленно завершится. В противном случае вы получите баллы в соответствии с разделом «Подзадачи».

Обратите внимание, что интерактор может быть адаптивным: истинные уровни мастерства велосипедистов могут меняться в процессе взаимодействия, но текущий набор уровней мастерства всегда будет согласован со всеми предыдущими соревнованиями.

Подзадачи

Для каждого набора входных данных пусть $q$ — количество проведенных вами соревнований. Кроме того, для каждого $N$ пусть $c_N$ — минимальное количество соревнований, необходимое для гарантированного определения уровней мастерства.

Вы получите 100 баллов, если $q \le c_N$ для всех наборов входных данных. В противном случае вы получите 10 баллов. Обратите внимание, что при ограничениях задачи для получения 10 баллов необходимо, чтобы $q \le N$ для всех наборов входных данных.

Примеры

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

1
5

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

? 1 2 3 4 5
3 2 1 0 1
? 1 3 5 2 4
3 1 2 1 0
? 1 4 2 5 3
3 0 1 2 1
? 1 5 4 3 2
3 1 0 1 2
! 4 2 1 5 3

Примечание

В примере уровни мастерства велосипедистов равны $4, 2, 1, 5, 3$ соответственно.

В первом проведенном соревновании велосипедисты выстроены в список $[1, 2, 3, 4, 5]$. Соревнование проходит следующим образом; в каждом раунде показан список велосипедистов, где выбывшие заменены на $X$.

• В раунде 1:
  • Велосипедист на позиции 3 (велосипедист 3 с уровнем 1) проигрывает велосипедистам на позициях 2 и 4 (велосипедисты 2, 4 с уровнями 2, 5) и выбывает.
  • Велосипедист на позиции 5 (велосипедист 5 с уровнем 3) проигрывает велосипедистам на позициях 4 и 1 (велосипедисты 4, 1 с уровнями 5, 4) и выбывает.
  • Велосипедист на позиции 1 (велосипедист 1 с уровнем 4) побеждает велосипедистов на позициях 5, 2 (велосипедисты 5, 2 с уровнями 3, 2) и поэтому не выбывает.
  • Велосипедист на позиции 2 (велосипедист 2 с уровнем 2) побеждает велосипедиста на позиции 3 (велосипедист 3 с уровнем 1) и поэтому не выбывает.
  • Велосипедист на позиции 4 (велосипедист 4 с уровнем 5) побеждает велосипедистов на позициях 3, 5 (велосипедисты 3, 5 с уровнями 1, 3) и поэтому не выбывает.
• В раунде 2 список велосипедистов: $[1, 2, X, 4, X]$.
  • Велосипедист на позиции 2 проигрывает велосипедистам на позициях 1 и 4 и выбывает.
  • Велосипедист на позиции 1 побеждает велосипедиста на позиции 2 и поэтому не выбывает.
  • Велосипедист на позиции 4 побеждает двух других велосипедистов и поэтому не выбывает.
• В раунде 3 список велосипедистов: $[1, X, X, 4, X]$.
  • Велосипедист на позиции 1 проигрывает велосипедистам на позициях 4 и 4 (которые являются одним и тем же велосипедистом) и выбывает.
  • Велосипедист на позиции 4 побеждает велосипедиста на позиции 1 и поэтому не выбывает.

Следовательно: Велосипедист на позиции 1 выбыл в раунде 3. Велосипедист на позиции 2 выбыл в раунде 2. Велосипедист на позиции 3 выбыл в раунде 1. Велосипедист на позиции 4 выиграл соревнование. * Велосипедист на позиции 5 выбыл в раунде 1.

Что дает ответ на запрос $[3, 2, 1, 0, 1]$.

Во втором проведенном соревновании велосипедисты выстроены в список $[1, 3, 5, 2, 4]$. Соревнование проходит следующим образом:

• В раунде 1:
  • Велосипедист на позиции 2 (велосипедист 3 с уровнем 1) проигрывает велосипедистам на позициях 1 и 3 (велосипедисты 1, 5 с уровнями 4, 3) и выбывает.
  • Велосипедист на позиции 4 (велосипедист 2 с уровнем 2) проигрывает велосипедистам на позициях 3 и 5 (велосипедисты 5, 4 с уровнями 3, 5) и выбывает.
  • Велосипедист на позиции 1 (велосипедист 1 с уровнем 4) побеждает велосипедиста на позиции 2 (велосипедист 3 с уровнем 1) и поэтому не выбывает.
  • Велосипедист на позиции 3 (велосипедист 5 с уровнем 3) побеждает велосипедистов на позициях 2, 4 (велосипедисты 3, 2 с уровнями 1, 2) и поэтому не выбывает.
  • Велосипедист на позиции 5 (велосипедист 4 с уровнем 5) побеждает велосипедистов на позициях 4, 1 (велосипедисты 2, 1 с уровнями 2, 4) и поэтому не выбывает.
• В раунде 2 список велосипедистов: $[1, X, 5, X, 4]$.
  • Велосипедист на позиции 3 проигрывает велосипедистам на позициях 1 и 5 и выбывает.
  • Велосипедист на позиции 1 побеждает велосипедиста на позиции 3 и поэтому не выбывает.
  • Велосипедист на позиции 5 побеждает двух других велосипедистов и поэтому не выбывает.
• В раунде 3 список велосипедистов: $[1, X, X, X, 4]$.
  • Велосипедист на позиции 1 проигрывает велосипедистам на позициях 5 и 5 (которые являются одним и тем же велосипедистом) и выбывает.
  • Велосипедист на позиции 5 побеждает велосипедиста на позиции 1 и поэтому не выбывает.

Следовательно: Велосипедист на позиции 1 выбыл в раунде 3. Велосипедист на позиции 2 выбыл в раунде 1. Велосипедист на позиции 3 выбыл в раунде 2. Велосипедист на позиции 4 выбыл в раунде 1. * Велосипедист на позиции 5 выиграл соревнование.

Что дает ответ на запрос $[3, 1, 2, 1, 0]$.