수고했어, 자기야. Little Cyan Fish는 자신의 암호가 얼마나 전달될지 모르겠지만, 그래도 여기까지 Little Cyan Fish와 함께 걸어와 준 것에 감사하고 있어. 너무나 많은 일들, 너무나 부조리한 일들이 일어났고, Little Cyan Fish는 지쳤어, 정말 많이 지쳤어... 지난 한 해 동안 Little Cyan Fish는 몇 번이나 스스로를 구원하려 한다고 느꼈지만, 결국 몸에 묶인 실을 끊어낼 만큼 강하지 못했어. Little Cyan Fish는 늘 저 머나먼 곳에 자신의 삶이라는 지도를 또렷이 내려다볼 수 있는 또 다른 자신이 있다고 상상하곤 해.

— "저 너머를 향한 동경" · 제10회 중국 대학생 프로그래밍 경시대회 결승전

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

자, 어쩌면 당신이 이것이 얼마나 어려울지 시도해 볼 수 있을 것입니다. Little Cyan Fish는 자신의 삶이 형태를 알 수 없는 순열이라고 느낍니다. 사람들은 늘 세상이 무작위성으로 가득 차 있다고 말하지만, 왜 Little Cyan Fish는 늘 이렇게 운이 없을까요...? 아하! 어쩌면 무작위성이란 원래 이렇게 심오한 것일지도 모릅니다! 그래서 Little Cyan Fish는 자신의 이 순열을 다음과 같은 방식으로 무작위 생성하기로 결정했습니다:

• 무작위 순열 $p_1, p_2, \dots, p_n$을 생성합니다: $1$부터 $n$까지의 가능한 모든 $n!$가지 순열 중에서 균등한 확률로 무작위 선택합니다.
• 만약 $p_1 > p_n$이면, 순열 전체를 뒤집습니다.

당신은 순열의 구조를 직접 관찰할 수 없지만, Little Cyan Fish는 당신에게 초능력을 부여했습니다: 바로 질문하기입니다! 매번 당신은 순열에서 두 수 사이의 거리를 $3$으로 나눈 나머지를 인터랙티브하게 질문할 수 있습니다. 구체적으로, 매번 두 수 $u, v$($1 \le u, v \le n$, $u \ne v$)를 선택하면, 순열은 이 두 수 사이의 거리를 $3$으로 나눈 나머지를 알려줍니다(즉, $p_i = u, p_j = v$를 만족하는 두 인덱스 $i, j$를 찾아 $|i - j| \bmod 3$을 답해줍니다).

이제 Little Cyan Fish는 당신이 무엇을 얻어낼 수 있는지 시도해 보기를 원합니다. 당신은 $25n$번 이하의 질문으로 이 순열을 알아내어 Little Cyan Fish를 도와야 합니다.

입력

여러 개의 테스트 케이스가 주어집니다. 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 하나의 정수 $T$($1 \le T \le 1000$)가 주어집니다.

각 테스트 케이스에 대해, 먼저 정수 $n$($3 \le n \le 10^4$)을 읽어야 합니다.

인터랙션 프로토콜

그다음 인터랙션이 시작됩니다. 각 테스트 케이스에서 최대 $25n$번의 질문을 할 수 있습니다. 질문을 하려면 질문을 나타내는 한 줄 ? u v($1 \le u, v \le n$, $u \ne v$)를 출력해야 합니다. 그런 다음 표준 입력으로부터 결과를 읽어야 합니다.

답을 제출하려면 ! p1 p2 ... pn을 출력해야 합니다. 당신의 출력은 반드시 $p_1 < p_n$을 만족해야 합니다. 답을 출력하는 것은 $25n$번의 질문 제한에 포함되지 않습니다. 답을 출력한 후에는 즉시 다음 테스트 케이스를 읽거나 즉시 프로그램을 종료해야 합니다.

질문을 출력한 후에는 줄바꿈 문자를 출력하고 출력 스트림을 플러시(flush)하는 것을 잊지 마세요. 이를 위해 C++에서는 fflush(stdout) 또는 cout.flush(), Java에서는 System.out.flush(), Pascal에서는 flush(output), Python에서는 stdout.flush()를 사용할 수 있습니다.

모든 테스트 케이스에서 $n$의 합은 $10^4$을 초과하지 않음이 보장됩니다.

이 문제에서 인터랙터는 비적응적(non-adaptive)임이 보장됩니다. 즉, 순열들은 인터랙션 과정이 시작되기 전에 문제에 설명된 대로 무작위로 결정되며, 당신의 질문에 따라 바뀌지 않습니다. (예제 테스트 케이스를 포함하여) 총 $30$개의 테스트 케이스가 있습니다.

예제

예제 입력 1

2
3
2
1
1
4
1
1
1
0
2

예제 출력 1

? 1 2
? 2 3
? 1 3
! 1 3 2
? 2 3
? 3 1
? 1 4
? 2 4
? 2 1
! 2 3 1 4

노트

그림 1: 2026년 3월 4일 <?>에서 촬영된 Little Cyan Fish와 <?>