G. Asem hates getting averaged (White)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem. You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout), in Java — System.out.flush(), in Pascal — flush(output), and in Python — sys.stdout.flush().

In this problem, the jury has a hidden permutation $$$p$$$ of length $$$n$$$. The permutation contains all integers from $$$1$$$ to $$$n$$$ exactly once. The value of $$$n$$$ is given to you at the beginning.

You can make queries to the testing system. Each query consists of two different indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$, $$$i \ne j$$$). After printing a query, you must flush the output stream.

For each query "? i j", the testing system responds with a single integer equal to $$$\lfloor \frac{p_i + p_j}{2} \rfloor$$$ where $$$p_i$$$ and $$$p_j$$$ are the values of the hidden permutation at positions $$$i$$$ and $$$j$$$.

When your program determines the entire permutation, print the string !$$$p_1\ p_2\ \dots\ p_n$$$, where $$$p_1, p_2, \dots, p_n$$$ is the reconstructed permutation, and terminate your program normally immediately after flushing the output stream.

Your program is allowed to make no more than $$$1.9n$$$ queries (not including printing the final answer) to the testing system.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t(1 \le t \le 10^4).$$$ The description of the test cases follows.

The first line contains an integer $$$n$$$ ($$$5 \le n \le 10^5$$$) — the length of the hidden permutation.

Each following line contains the response to one of your queries. The $$$i$$$-th such line is the response to your $$$i$$$-th query and contains a single integer equal to $$$\lfloor \frac{p_i + p_j}{2} \rfloor$$$ where $$$(x_i, y_i)$$$ is the pair of indices printed in your $$$i$$$-th query.

The testing system will allow you to read the response to a query only after your program prints the query and performs the flush operation.

When your program prints the final answer using the format ! $$$p_1 p_2 \dots p_n$$$, it must terminate immediately.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$10^5$$$ over all test cases.

Output

To make the queries, your program must use standard output.

Each query must be printed in the format "? i j", where $$$1 \le i, j \le n$$$ and $$$i \ne j$$$. Print exactly one query per line and perform the flush operation after each query.

The response to the query will be provided on standard input after you flush the output.

When your program has reconstructed the permutation, print the final answer in the format ! $$$p_1 p_2 \dots p_n$$$, where $$$p_1, p_2, \dots, p_n$$$ is the permutation, flush the output, and terminate your program.

Example
Input
1
5

3

3

2

1
Output
? 1 5

? 2 3

? 2 5

? 4 5

! 5 4 3 2 1
Note

In the sample test case, suppose the hidden permutation is $$$p = [5, 4, 3, 2, 1]$$$.

Each query ? i j returns $$$\lfloor \frac{p_i + p_j}{2} \rfloor$$$.

Now let us verify the sample interaction.

For the query ? 1 5, $$$\lfloor \frac{5 + 1}{2} \rfloor = \lfloor \frac{6}{2} \rfloor = 3$$$.

For the query ? 2 3, $$$\lfloor \frac{4 + 3}{2} \rfloor = \lfloor \frac{7}{2} \rfloor = 3$$$.

For the query ? 2 5, $$$\lfloor \frac{4 + 1}{2} \rfloor = \lfloor \frac{5}{2} \rfloor = 2$$$.

For the query ? 4 5, $$$\lfloor \frac{2 + 1}{2} \rfloor = \lfloor \frac{3}{2} \rfloor = 1$$$.

Thus, all responses are consistent with the permutation ! 5 4 3 2 1.