Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

O. Hidden Permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem. Refer to the Interaction Protocol section below for better understanding.

Sherbiny has hidden a secret permutation $$$p$$$ of length $$$n$$$ (an array containing every integer from 1 to $$$n$$$ exactly once). Luffy's task is to reconstruct this permutation using at most $$$n-1$$$ queries.

Luffy cannot see the elements of $$$p$$$, but he can ask Sherbiny to evaluate specific subsets of indices. When Luffy queries a subset, Sherbiny isolates the elements at those indices—keeping them in their original relative order—and tells Luffy exactly how many inversions exist just among those isolated elements.

Formal Query Definition: Specifically, if Luffy queries a subset of $$$k$$$ indices $$$1 \le i_{1} \lt i_{2} \lt \dots \lt i_{k} \le n$$$, Sherbiny constructs a new sequence $$$a = [p_{i_{1}}, p_{i_{2}}, \dots, p_{i_{k}}]$$$. Sherbiny then returns the total number of inversions in $$$a$$$.

The number of inversions in an array is the number of pairs of indices $$$u, v$$$ such that $$$u \lt v$$$ and $$$a_{u} \gt a_{v}$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of the test cases follows.

For each test case, Sherbiny first outputs a single integer $$$n$$$ ($$$2 \le n \le 1000$$$) — the length of the hidden permutation.

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

Output

For each test case, after at most $$$n-1$$$ questions, output one line:

  • ! $$$p_1$$$ $$$p_2$$$ $$$\ldots$$$ $$$p_n$$$
where $$$p_1, p_2, \ldots, p_n$$$ must be a permutation of the integers from $$$1$$$ to $$$n$$$ and must match the hidden permutation.
Interaction

For each test case, after reading $$$n$$$, you may ask at most $$$n-1$$$ questions before you must output your guess.

To ask a question, output a line in the following format:

  • ? $$$k$$$ $$$i_1$$$ $$$i_2$$$ $$$\ldots$$$ $$$i_k$$$
where $$$k$$$ ($$$1 \leq k \leq n$$$) is the number of chosen positions, and $$$i_1, i_2, \ldots, i_k$$$ are distinct integers from $$$1$$$ to $$$n$$$.

After each question, read one integer from the judge — the number of inversions among the values at the chosen positions.

After printing each line, flush the output. For example:

  • cout « endl or fflush(stdout) in C++;
  • System.out.flush() in Java;
  • sys.stdout.flush() in Python.

When you have determined the hidden permutation, output a single line:

  • ! $$$p_1$$$ $$$p_2$$$ $$$\ldots$$$ $$$p_n$$$
where $$$p_1, p_2, \ldots, p_n$$$ is your guess for the permutation. After outputting !, do not ask any more questions for the current test case; proceed to the next test case if one remains.
Example
Input
2
3

1

0

2

1
Output
? 2 1 3

? 2 2 3

! 3 1 2

? 2 1 2

! 2 1
Note

In the example, the judge first sends $$$t = 2$$$. The hidden permutations are $$$[3, 1, 2]$$$ in the first test case and $$$[2, 1]$$$ in the second test case.

ParticipantJudge
$$$2$$$
$$$3$$$
? 2 1 3
$$$1$$$
? 2 2 3
$$$0$$$
! 3 1 2
$$$2$$$
? 2 1 2
$$$1$$$
! 2 1

In the first test case, $$$n = 3$$$ and the hidden permutation is $$$[3, 1, 2]$$$. The question ? 2 1 3 asks about positions $$$1$$$ and $$$3$$$, whose values are $$$3$$$ and $$$2$$$; there is one inversion because $$$3 \gt 2$$$, so the judge replies with $$$1$$$. The question ? 2 2 3 asks about positions $$$2$$$ and $$$3$$$, whose values are $$$1$$$ and $$$2$$$; there are no inversions, so the judge replies with $$$0$$$. The participant then outputs ! 3 1 2.

In the second test case, $$$n = 2$$$ and the hidden permutation is $$$[2, 1]$$$. The question ? 2 1 2 selects both positions; the values $$$2$$$ and $$$1$$$ form one inversion, so the judge replies with $$$1$$$. The participant outputs ! 2 1.

Note that the participant uses only $$$2 = n - 1$$$ questions in the first test case and $$$1 = n - 1$$$ question in the second test case.

Empty lines in the example input and output are shown only for readability. Your solution must not output blank lines.