Description:
This is an interactive problem!
Nastia has a hidden permutation $$$p$$$ of length $$$n$$$ consisting of integers from $$$1$$$ to $$$n$$$. You, for some reason, want to figure out the permutation. To do that, you can give her an integer $$$t$$$ ($$$1 \le t \le 2$$$), two different indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$, $$$i \neq j$$$), and an integer $$$x$$$ ($$$1 \le x \le n - 1$$$).
Depending on $$$t$$$, she will answer:
- $$$t = 1$$$: $$$\max{(\min{(x, p_i)}, \min{(x + 1, p_j)})}$$$;
- $$$t = 2$$$: $$$\min{(\max{(x, p_i)}, \max{(x + 1, p_j)})}$$$.
You can ask Nastia at most $$$\lfloor \frac {3 \cdot n} { 2} \rfloor + 30$$$ times. It is guaranteed that she will not change her permutation depending on your queries. Can you guess the permutation?
Input Format:
The input consists of several test cases. In the beginning, you receive the integer $$$T$$$ ($$$1 \le T \le 10\,000$$$) — the number of test cases.
At the beginning of each test case, you receive an integer $$$n$$$ ($$$3 \le n \le 10^4$$$) — the length of the permutation $$$p$$$.
It's guaranteed that the permutation is fixed beforehand and that the sum of $$$n$$$ in one test doesn't exceed $$$2 \cdot 10^4$$$.
Output Format:
None
Note:
Consider the first test case.
The hidden permutation is $$$[3, 1, 4, 2]$$$.
We print: "? $$$2$$$ $$$4$$$ $$$1$$$ $$$3$$$" and get back $$$\min{(\max{(3, p_4}), \max{(4, p_1)})} = 3$$$.
We print: "? $$$1$$$ $$$2$$$ $$$4$$$ $$$2$$$" and get back $$$\max{(\min{(2, p_2)}, \min{(3, p_4)})} = 2$$$.
Consider the second test case.
The hidden permutation is $$$[2, 5, 3, 4, 1]$$$.
We print: "? $$$2$$$ $$$3$$$ $$$4$$$ $$$2$$$" and get back $$$\min{(\max{(2, p_3}), \max{(3, p_4)})} = 3$$$.