E. Mr.Wow and Hidden Permutation
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

Mr. Cow has a hidden permutation $$$p$$$ of length $$$n$$$. It is guaranteed that $$$\bf{n\ mod\ 4 = 2}$$$.

Mr. Wow doesn't know anything about this permutation. Mr. Cow asked him to find any permutation $$$q$$$ of length $$$n$$$, such that $$$f(p,q)=|p_{q_{1}} - p_{q_{2}}| + |p_{q_{2}} - p_{q_{3}}| + \ldots +|p_{q_{n-1}} - p_{q_{n}}| + |p_{q_{n}} - p_{q_{1}}| $$$ is maximum possible.

To find the permutation $$$q$$$, Mr. Wow is allowed to ask the following question to Mr.Cow:

  • $$$? \ i_1 \ i_2 \ .... \ i_{(\frac{n}{2}-1)} \ i_{(\frac{n}{2})} \ (1 \le i_j \le n, 1 \le j \le \frac{n}{2}, i_{j} ≠ i_{k}$$$ for $$$j ≠ k)$$$. In other words, he will give exactly $$$(\frac{n}{2})$$$ distinct indices to Mr. Cow. After that, Mr. Cow will give him the median of $$$p_{i_1} , p_{i_2} , \ldots , p_{i_{(\frac{n}{2}-1)}} , p_{i_{(\frac{n}{2})}}$$$.

Help Mr. Wow to find any permutation $$$q$$$ such that $$$f(p,q)$$$ reaches maximum by asking at most $$$n + 30$$$ questions.

Input

The first line contains an integer $$$t(1 \le t \le 100)$$$, denoting the number of test cases.

For each test case, the only line contains a single integer $$$n$$$ $$$(2 \le n \le 1002)$$$ — the length of the hidden permutation. It is guaranteed that $$$\bf{n\ mod\ 4 = 2}$$$.

It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$1002$$$.

Interaction

For each test case, the interaction starts with reading $$$n$$$.

Then you are allowed to ask atmost $$$n+30$$$ queries of the following way

$$$? \ i_1 \ i_2 \ .... \ i_{(\frac{n}{2}-1)} \ i_{(\frac{n}{2})}$$$.

After each query, you should read an integer : the median of $$$p_{i_1} , p_{i_2} , \ldots , p_{i_{(\frac{n}{2}-1)}} , p_{i_{(\frac{n}{2})}}$$$.

When you guessed any permutation $$$q$$$, print a single line $$$! \ q_1 \ q_2 \ .... \ q_{n-1} \ q_{n}$$$.

Outputting the answer does not count as a query.

The interactor for this problem is not adaptive. The permutation $$$p$$$ is fixed before any queries are made.

After printing a query, do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
2

6

3

5

6

2

4
Output

? 6 2 5

? 2 4 1

! 4 6 1 5 2 3

? 4 3 5

? 1 6 2

! 4 2 1 6 3 5
Note

The hidden permutation in the $$$1$$$-st test case is $$$p=[5,6,2,4,1,3]$$$.

For $$$q=[4,6,1,5,2,3]$$$, $$$f(p,q)=|p_4-p_6|+|p_6-p_1|+|p_1-p_5|+|p_5-p_2|+|p_2-p_3|+|p_3-p_4|=1+2+4+5+4+2=18$$$.

It can be proven $$$18$$$ is the maximum of $$$f(p,q)$$$.

The hidden permutation in the $$$2$$$-nd test case is $$$p=[3,4,1,2,5,6]$$$.