E2. Mexness (Hard Version)
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is the hard version of the problem. The only difference is the maximum number of queries.

This is an interactive problem.

There is a secret permutation $$$p_0, p_1, \ldots, p_{n-1}$$$, which is a permutation of $$$\{0,1,\ldots,n-1\}$$$. There is also a variable $$$mx$$$. At first, $$$mx=4$$$.

Your task is to guess the permutation by using queries of the following type:

  • "! $$$i$$$ $$$v$$$" — you answer $$$p_i$$$ $$$(0 \le i \lt n)$$$ is equal to $$$v$$$ $$$(0 \le v \lt n)$$$. If your answer is incorrect, or you have answered twice for the same $$$p_i$$$, the jury will immediately terminate the program and you will receive Wrong Answer. Otherwise, the jury will increase $$$mx$$$ by $$$1$$$.
  • "? $$$k$$$ $$$j_1$$$ $$$j_2$$$ $$$\dots$$$ $$$j_k$$$" — select the integer $$$k$$$ ($$$1 \le k \le n$$$) and $$$k$$$ indices $$$j_1$$$, $$$j_2$$$, $$$\dots$$$, $$$j_k$$$ ($$$0 \le j_i \lt n$$$). In response to the query, the jury will return $$$\min(mx,$$$$$$\text{mex}(p_{j_1}, p_{j_2}, \dots, p_{j_k}))$$$.

The $$$\text{mex}(a)$$$ of an array $$$a$$$ is defined as the smallest non-negative integer that does not appear in $$$a$$$. For example, if $$$a = [0, 1, 2, 4]$$$, then $$$\text{mex}(a) = 3$$$ because $$$3$$$ is the smallest non-negative integer not present in $$$a$$$.

Find out the secret permutation using at most $$$7n$$$ queries of the second type.

Input

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

Interaction

The first line of each test case contains one integer $$$n$$$ ($$$2 \le n \le 1024$$$). It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$1024$$$.

At this moment, the permutation $$$p_0, p_1, \ldots, p_{n-1}$$$ is chosen. The interactor in this task is not adaptive. In other words, the sequence $$$p$$$ is fixed in every test case and does not change during the interaction.

Then you can make queries.

To make a query of the first type, output a line in the format "! $$$i$$$ $$$v$$$" (without quotes). Note that this line is not included in the count of $$$7n$$$ queries of the second type.

To make a query of the second type, output a line in the format "? $$$k$$$ $$$j_1$$$ $$$j_2$$$ $$$\dots$$$ $$$j_k$$$" (without quotes) ($$$1 \le k \le n$$$, $$$0 \le j_i \lt n$$$). After each query, read an integer — the answer to your query.

After performing $$$n$$$ queries of the first type (in other words, you have guessed the entire permutation $$$p$$$), if this is the last test case, the jury will terminate the program. Otherwise, the jury will output the next $$$n$$$.

After printing each line, do not forget to output the end of line and flush the output buffer. Otherwise, you will receive the Idleness limit exceeded verdict. To flush, use:

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

1


0


2

1
Output


? 2 1 0

! 2 1
? 1 0

! 0 2
! 1 0

? 1 0

! 0 0
! 1 1
Note

In the first test case, the hidden permutation $$$p$$$ is $$$[2,0,1]$$$.

For the query "? 2 1 0", the jury returns $$$1$$$ because $$$\min(mx,\text{mex}(p_1,p_0)) = \min(4,1) =1$$$.

Then, for answer "! 2 1", the jury increases $$$mx$$$ by $$$1$$$ since the answer is correct and you haven't answered for $$$p_2$$$ twice.

For the query "? 1 0", the jury returns $$$0$$$ because $$$\min(mx,\text{mex}(p_0))=\min(5,0) =0$$$.

Note queries are only for understanding statements and do not guarantee finding a unique permutation $$$p$$$.