This is an interactive problem.

There is a secret permutation $p$ ($1$-indexed) of numbers from $1$ to $n$. More formally, for $1 \leq i \leq n$, $1 \leq p[i] \leq n$ and for $1 \leq i < j \leq n$, $p[i] \neq p[j]$. It is known that $p[1]<p[2]$.

In $1$ query, you give $3$ distinct integers $a,b,c$ ($1 \leq a,b,c \leq n$), and receive the median of $\{|p[a]-p[b]|,|p[b]-p[c]|,|p[a]-p[c]|\}$.

In this case, the median is the $2$-nd element ($1$-indexed) of the sequence when sorted in non-decreasing order. The median of $\{4,6,2\}$ is $4$ and the median of $\{0,123,33\}$ is $33$.

Can you find the secret permutation in not more than $2n+420$ queries?

Note: the grader is not adaptive: the permutation is fixed before any queries are made.

The first line of input contains a single integer $t$ $(1 \leq t \leq 1000)$ — the number of testcases.

The first line of each testcase consists of a single integer $n$ $(20 \leq n \leq 100000)$ — the length of the secret permutation.

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

Interaction

For each testcase, you begin the interaction by reading $n$.

To perform a query, output "? a b c" where $a,b,c$ is the $3$ indices you want to use for the query.

Numbers have to satisfy $1 \leq a,b,c \leq n$ and $a \neq b$,$b \neq c$,$a \neq c$.

For each query, you will receive a single integer $x$: the median of $\{|p[a]-p[b]|,|p[b]-p[c]|,|p[a]-p[c]|\}$.

In case your query is invalid or you asked more than $2n+420$ queries, the interactor will print "−1" and will finish interaction. You will receive Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts.

When you have determined the secret permutation, output "! p[1] p[2] ... p[n]". If the secret permutation is correct, the interactor will print "1". Otherwise, the interactor will print "-1" and will finish interaction. You will receive Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts.

After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded verdict.

To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

Hacks:

To hack, use the following format of test:

The first line should contain a single integer $t$ ($1 \leq t \leq 1000$) — the number of testcases.

The first line of each testcase should contain a single integer $n$ ($20 \leq n \leq 100000$) — the length of the secret permutation.

The following line of should contain $n$ integers $p[1],p[2],p[3],\ldots,p[n]$. $p[1]<p[2]$ and $p$ must be a permutation of integers from $1$ to $n$.

You must ensure that the sum of $n$ over all testcases does not exceed $100000$.