이 문제는 인터랙티브 문제입니다.

VegiCat은 각 원소가 $0$, $1$, 또는 $2$인 배열 $a_1, a_2, \ldots, a_n$을 알고 있습니다. 그는 배열의 값을 직접 알려주지 않지만, 당신은 그에게 질문을 할 수 있습니다. 각 질의에서 두 인덱스 $i$와 $j$를 선택하면, VegiCat은 $a_i > a_j$인지 여부를 알려줍니다.

VegiCat은 대응하는 배열 값의 비내림차순으로 인덱스를 출력하라고 요청합니다. 즉, 다음을 만족하는 $1, 2, \ldots, n$의 순열 $p_1, p_2, \ldots, p_n$을 찾으세요:

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

각 테스트 케이스에서 최대 $2n - 3$번의 질의를 할 수 있습니다.

인터랙터는 적응형(adaptive)입니다. 이는 배열이 사전에 고정되어 있지 않음을 의미합니다. 인터랙터는 지금까지 주어진 모든 응답과 모순되지 않고 원소가 $\{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$입니다. 각 질의 후에는 정수 하나를 읽어야 합니다:

• $a_i > a_j$이면 $1$;
• $a_i \le a_j$이면 $0$.

$i = j$인 질의와 중복된 질의도 허용되며 질의 횟수에 포함됩니다.

순서를 결정했다면 다음 형식의 한 줄을 출력하세요:

! p_1 p_2 ... p_n

$1$부터 $n$까지의 각 인덱스가 정확히 한 번씩 나타나야 합니다. 답을 출력하는 것은 질의 횟수에 포함되지 않습니다.

답이 올바르면 다음 테스트 케이스의 $n$을 읽어 다음 테스트 케이스를 진행하고, 마지막 테스트 케이스였다면 프로그램을 종료하세요. 인터랙터는 답 출력 후 별도의 확인 응답을 보내지 않습니다.

각 질의나 답을 출력한 후에는 줄바꿈을 출력하고 출력 버퍼를 비워야(flush) 합니다. 출력 버퍼를 비우려면 다음을 사용할 수 있습니다:

• C/C++에서는 fflush(stdout) 또는 cout.flush();
• Java와 Kotlin에서는 System.out.flush();
• Python에서는 sys.stdout.flush().

유효하지 않은 질의를 하거나, 질의 횟수 제한을 초과하거나, 잘못된 답을 출력하면 Wrong Answer 판정을 받게 됩니다. 지정된 형식을 따르지 않는 출력 또한 Wrong Answer로 판정됩니다. 이러한 경우 인터랙터는 오류 응답을 보내지 않고 즉시 종료됩니다.

예제

입력 1

2
3

1

1

2

0

출력 1

? 1 2

? 2 3

! 3 2 1

? 1 2

! 1 2

참고

첫 번째 테스트 케이스에서 질의 ? 1 2와 ? 2 3은 모두 $1$을 반환하므로 $a_1 > a_2 > a_3$입니다. 따라서 $(3, 2, 1)$은 올바른 답입니다.

두 번째 테스트 케이스에서 질의 ? 1 2는 $0$을 반환하므로 $a_1 \le a_2$입니다. 따라서 $(1, 2)$는 올바른 답입니다.