Description:
This is an interactive problem.
Jury initially had a sequence $$$a$$$ of length $$$n$$$, such that $$$a_i = i$$$.
The jury chose three integers $$$i$$$, $$$j$$$, $$$k$$$, such that $$$1 \leq i < j < k \leq n$$$, $$$j - i > 1$$$. After that, Jury reversed subsegments $$$[i, j - 1]$$$ and $$$[j, k]$$$ of the sequence $$$a$$$.
Reversing a subsegment $$$[l, r]$$$ of the sequence $$$a$$$ means reversing the order of elements $$$a_l, a_{l+1}, \ldots, a_r$$$ in the sequence, i. e. $$$a_l$$$ is swapped with $$$a_r$$$, $$$a_{l+1}$$$ is swapped with $$$a_{r-1}$$$, etc.
You are given the number $$$n$$$ and you should find $$$i$$$, $$$j$$$, $$$k$$$ after asking some questions.
In one question you can choose two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) and ask the number of inversions on the subsegment $$$[l, r]$$$ of the sequence $$$a$$$. You will be given the number of pairs $$$(i, j)$$$ such that $$$l \leq i < j \leq r$$$, and $$$a_i > a_j$$$.
Find the chosen numbers $$$i$$$, $$$j$$$, $$$k$$$ after at most $$$40$$$ questions.
The numbers $$$i$$$, $$$j$$$, and $$$k$$$ are fixed before the start of your program and do not depend on your queries.
Input Format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. Description of the test cases follows.
The single line of each test case contains a single integer $$$n$$$ ($$$4 \leq n \leq 10^9$$$). After reading it you should start an interaction process by asking questions for that test case. After giving an answer you should:
- Terminate your program if that is the last test case.
- Proceed to the next test case otherwise.
Output Format:
None
Note:
In the first test case, $$$i = 1$$$, $$$j = 3$$$, $$$k = 5$$$, so the sequence $$$a$$$ is $$$[2, 1, 5, 4, 3]$$$.
In the second test case, $$$i = 2$$$, $$$j = 4$$$, $$$k = 5$$$, so the sequence $$$a$$$ is $$$[1, 3, 2, 5, 4]$$$.