This is the hard version of the problem. The difference between the versions is that in this version, you can make at most $$$10\cdot n$$$ queries. You can hack only if you solved all versions of this problem.

Ali loved Bahamin's gift (from problem E) so much that he illegally traveled from Qazvin to Liverpool to have the gift signed by football players. Now Interpol is searching for him, but they've offered a deal: solve a problem, and he can stay in Liverpool. But since he's currently at the stadium, he can't solve it — so he asked you to do it.

This is an interactive problem.

There is a hidden permutation$$$^{\text{∗}}$$$ $$$p$$$ of length $$$n\ge 4$$$, where $$$p_i \neq i$$$ for each $$$1 \leq i \leq n$$$.

Initially, you should give the jury a positive integer $$$k\le n$$$, which will be constant through future queries. Then you need to find permutation $$$p$$$ using some queries.

In each query, you give a permutation $$$q_1, q_2, \ldots, q_n$$$ to the jury. In response, you will receive the number of pairs $$$(i, j)$$$ such that all of the following conditions hold:

$$$i \lt j$$$;
$$$p_{q_i} = q_j$$$;
$$$i \neq k$$$. ($$$k$$$ is the constant you have given to the jury)

You are given $$$n$$$, and you need to find the permutation $$$p$$$ in at most $$$10\cdot n$$$ queries.

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

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

The only line of each test case contains a single integer $$$n$$$ ($$$4 \leq n \leq 100$$$) — the length of $$$p$$$.

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

Interaction

The interaction for each test case begins with reading the integer $$$n$$$.

Then you should output the integer $$$k$$$ ($$$1 \leq k \leq n$$$). This is not considered as a query.

Then you can ask up to $$$10\cdot n$$$ queries.

To make a query, output a line in the following format:

$$$\texttt{?}\,q_1\,q_2\,\ldots\,q_n$$$

The jury will return the answer to the query.

When you find the permutation $$$p$$$, output a single line in the following format:

$$$\texttt{!}\,p_1\,p_2\,\ldots\,p_n$$$

This is also not considered as a query.

After that, proceed to process the next test case or terminate the program if it is the last test case.

The interactor is not adaptive, which means that the permutation is determined before the participant outputs $$$k$$$.

If your program makes more than $$$10\cdot n$$$ queries, your program should immediately terminate to receive the verdict Wrong answer. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing each query do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict.

If, at any interaction step, you read $$$-1$$$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

Hacks

To perform a hack, use the following format:

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

The first line of each test case contains a single integer $$$n$$$ ($$$4 \leq n \leq 100$$$) — the length of $$$p$$$.

The second line contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, $$$p_i\ne i$$$, all $$$p_i$$$-s are distinct) — the permutation $$$p$$$.

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

$$$^{\text{∗}}$$$To flush, use:

fflush(stdout) or cout.flush() in C++;
sys.stdout.flush() in Python;
see the documentation for other languages.

Note

In the first test case, $$$p = [3, 1, 4, 2]$$$. The solution selected $$$k=1$$$, then it asked permutation $$$q = [1, 2, 3, 4]$$$. Only pair $$$(3,4)$$$ satisfies the conditions.

In the second test case, $$$p = [3, 1, 2, 5, 4]$$$. The solution selected $$$k=3$$$.

For permutation $$$q = [1, 2, 5, 4, 3]$$$, only pair $$$(1, 5)$$$ satisfies the conditions.
For permutation $$$q = [2, 1, 4, 3, 5]$$$, pairs $$$(1, 2)$$$ and $$$(2, 4)$$$ satisfy the conditions.

#	Name	Rating↕	Solved↕
2127G2	Inter Active (Hard Version) binary search bitmasks constructive algorithms graphs implementation interactive math probabilities	3500	126
1842H	Tenzing and Random Real Numbers bitmasks dp graphs math probabilities	3000	1.1k
1556F	Sports Betting bitmasks combinatorics dp graphs math probabilities	2500	1.5k

Problemset