This is an interactive problem.
Two elements at positions and (1\le i<j\le n) have been swapped in the permutation p=(1,2,\ldots,n).
In one query, you may choose a segment [l,r] and find the number of inversions in p_l,p_{l+1},\ldots,p_r, that is, the number of index pairs such that l\le u<v\le r and p_u>p_v.
Find and using at most queries per test case. The hidden permutation is fixed before the interaction starts and does not change.
First, the interactor sends one integer (1\le t\le100) — the number of test cases.
Before each test case, the interactor sends one integer (2\le n\le10^4) — the permutation length. The values and are hidden.
To make a query, print a separate line ? l r, where 1\le l\le r\le n. The interactor replies with one integer — the number of inversions on this segment.
When you find the answer, print a separate line ! i j, where 1\le i<j\le n. Printing the answer does not count as a query.
After a correct answer, the interactor immediately sends for the next test case, if any. There is no additional acknowledgement. After answering the last test case, terminate your program.
After each command, print a newline and flush the output buffer, for example using cout.flush() in C++ or flush=True in Python.
An invalid command, an incorrect answer, or exceeding the query limit results in Wrong Answer. Each command must contain exactly two integer parameters. If you receive or reach the end of the input stream, terminate your program immediately.
Example 1
Example 2
Example 3
In the examples, the input column contains the interactor's messages, and the output column contains the program's commands in their execution order.
In the first example, p=(1,4,3,2,5). The interactor first sends t=1 and n=5. It replies to both ? 1 5 and ? 2 4, after which the program prints ! 2 4.
In the second example, p=(2,1). In the third example, p=(4,2,3,1): the entire segment has inversions, whereas the segment has .
Subtask ( points): n\le4.
Subtask ( points): n\le15.
Subtask ( points): i=1.
Subtask ( points): no additional constraints.