F. XOR Permutations
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

There is a hidden permutation$$$^†$$$ $$$p$$$ of size $$$n$$$.

You can make queries of another permutation $$$q$$$ of size $$$n$$$. The interactor will calculate and give you $$$\sum_{i=1}^{n} p_i \oplus q_i$$$.

Using at most $$$\frac{5n}{2}$$$ queries, find the hidden permutation $$$p$$$ and output it.

$$$^†$$$An array $$$a$$$ is a permutation of size $$$n$$$ if it contains each of the elements $$$0, 1, 2, ..., n-1$$$ exactly once.

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.

The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the size of the hidden permutation $$$p$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases is at most $$$1000$$$.

Interaction

You can make queries in the following format — to query a permutation $$$q$$$, output one line of the form "? $$$q_1$$$ $$$q_2$$$ ... $$$q_n$$$" (where $$$q$$$ is a permutation of size $$$n$$$). After that, read a single integer — the value of $$$\Sigma_{i=1}^{n} p_i \oplus q_i$$$.

To report the hidden permutation as $$$q$$$, output "! $$$q_1$$$ $$$q_2$$$ ... $$$q_n$$$" (where $$$q$$$ is a permutation of size $$$n$$$). Then, the interaction continues with the next test case.

Reporting the answer does not count towards the number of queries made.

Note that you have to use the flush operation right after printing each line — otherwise you may get Idleness Limit Exceeded verdict. For example, in C++ you should use the function fflush(stdout) or cout.flush(), in Java or Kotlin — System.out.flush(), and in Python — sys.stdout.flush().

Example
Input
3
# Test case 1
4
0

# Test case 2
3
6
6
2

# Test case 3
6
16
Output
# Test case 1
? 2 0 1 3
! 2 0 1 3

# Test case 2
? 0 1 2
? 1 2 0
? 2 1 0
! 2 0 1

# Test case 3
? 0 1 2 3 4 5
! 3 1 4 2 5 0
Note

You do not have to handle comments (lines starting with #) in the input; they are only for presentation purposes and will not be present in the test cases.

The queries given in the sample input and output are for demonstrating the interaction, and may not logically lead to a correct output.

  • Test case 1: The hidden permutation is $$$p = [2, 0, 1, 3]$$$.
    • The participant's code makes a query with $$$q = [2, 0, 1, 3]$$$. The interactor calculates and returns $$$\sum_{i=1}^{n} p_i \oplus q_i = 0 + 0 + 0 + 0 = 0$$$.

    The participant's code correctly concludes that the hidden permutation is $$$[2, 0, 1, 3]$$$ and outputs it.

  • Test case 2: The hidden permutation is $$$p = [2, 0, 1]$$$.
    • The participant's code makes a query with $$$q = [0, 1, 2]$$$. The interactor calculates and returns $$$\sum_{i=1}^{n} p_i \oplus q_i = 2 + 1 + 3 = 6$$$.
    • The participant's code makes a query with $$$q = [1, 2, 0]$$$. The interactor calculates and returns $$$\sum_{i=1}^{n} p_i \oplus q_i = 3 + 2 + 1 = 6$$$.
    • The participant's code makes a query with $$$q = [2, 1, 0]$$$. The interactor calculates and returns $$$\sum_{i=1}^{n} p_i \oplus q_i = 0 + 1 + 1 = 2$$$.

    The participant's code correctly concludes that the hidden permutation is $$$[2, 0, 1]$$$ and outputs it.

  • Test case 3: The hidden permutation is $$$p = [3, 1, 4, 2, 5, 0]$$$.
    • The participant's code makes a query with $$$q = [0, 1, 2, 3, 4, 5, 6]$$$. The interactor calculates and returns $$$\sum_{i=1}^{n} p_i \oplus q_i = 3 + 0 + 6 + 1 + 0 + 6 = 16$$$.

    The participant's code correctly concludes that the hidden permutation is $$$[3, 1, 4, 2, 5, 0]$$$ and outputs it.