D. Guess the permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

In the mystical kingdom of Numeria, a powerful oracle has concealed a secret sequence — a hidden permutation $$$p$$$. The kingdom's future depends on deciphering this sequence, for it holds the key to unlocking the legendary Vault of Order, a chamber said to contain untold wisdom and treasures.

As the kingdom's greatest mathematician, you have been chosen for this task. However, the oracle does not reveal secrets so easily. Instead, she offers a challenge:

"For any query, you may choose three distinct indices $$$i,j,k$$$ where $$$ 1 \le i,j,k \le n$$$, and I shall reveal the sum $$$p_i + p_j + p_k$$$."

Your task is to determine the hidden permutation $$$p$$$ in no more than $$$n$$$ queries.

Input

The first line of each testcase contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of testcases. Description of each testcase follows.

Interaction

The interaction begins with reading $$$n$$$ $$$(4 \le n \le 10^4)$$$ — the length of hidden permutation $$$p$$$.

It is guaranteed that the sum of $$$n$$$ over all testcases do not exceed $$$10^4$$$.

The permutation $$$p$$$ is fixed for each testcase. In other words, the interactor is not adaptive.

It is guaranteed that $$$p$$$ is a permutation.

To make a query, output "? i j k" (without quotes, $$$1 \le i,j,k \le n,i \neq j \neq k \neq i$$$). Then you must read the response to the query, which is equal to $$$p_i + p_j + p_k$$$.

To give an answer, output "! $$$p_1$$$ $$$p_2$$$ $$$p_3$$$ ... $$$p_n$$$" where $$$p_1,p_2,p_3 \cdots p_n$$$ represent the hidden permutation $$$p$$$.

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 make an invalid query or make more queries than the given limit, then the program will terminate immediately and you will receive Wrong Answer verdict.

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

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

8

10

6

11

11

6
Output

? 5 1 2

? 1 4 3

! 3 1 2 5 4

? 4 5 6

? 3 1 4

? 5 2 3

! 6 3 1 4 2 5
Note

In the first testcase, $$$p = [3,1,2,5,4]$$$.

In the second testcase, $$$p = [6,3,1,4,2,5]$$$.