G. Find the Second Maximum
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

There is a hidden array $$$a$$$ of length $$$n$$$, consisting of distinct positive integers no larger than $$$10^9$$$. Your task is to find the second maximum element of $$$a$$$. To achieve this, you may query a non-empty range $$$[l,r]$$$ $$$(1 \le l \le r \le n)$$$, and the judge will return you the maximum element among $$$a_l, a_{l+1}, \ldots, a_r$$$.

You may not use more than $$$24$$$ queries.

Input

Each test contains multiple test cases. The first line contains one integer $$$t$$$ ($$$1\le t\le500$$$) — the number of test cases. The description of each test case follows.

The first line of each test case contains one integer $$$n$$$ ($$$2\le n\le1000$$$) — the length of the hidden array $$$a$$$.

Interaction

To ask a query, output a line in the following format:

  • ? l r

where $$$[l,r]$$$ is the query range.

After each query, you should read one line containing one integer, denoting the maximum element among $$$a_l,a_{l+1},\ldots,a_r$$$.

Print the answer in a line in the following format:

  • ! x i

where $$$x$$$ is the value of the second maximum element, and $$$i$$$ ($$$1 \le i \le n$$$) is the index of $$$x$$$ in $$$a$$$.

Note that printing the answer is not counted towards the total number of queries.

You can ask at most $$$24$$$ queries in each test case.

The interactor is NOT adaptive, meaning that the answer is known before the participant asks the queries and doesn't depend on the queries asked by the participant.

If your program makes more than $$$24$$$ queries for one test case, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. 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 the documentation for other languages.
Example
Input
1
10

9

10

6

1
Output


? 1 3

? 2 10

? 9 10

? 3 3

! 9 1
Note

In the sample test case, the hidden array $$$a$$$ is $$$[9,8,1,3,2,10,5,7,6,4]$$$.

  • In the first query, the maximum element among $$$a_1,a_2,a_3$$$ is $$$9$$$.
  • In the second query, the maximum element among $$$a_2,a_3,\ldots,a_{10}$$$ is $$$10$$$.
  • In the third query, the maximum element among $$$a_9,a_{10}$$$ is $$$6$$$.
  • In the fourth query, the maximum element among $$$a_3$$$ is $$$1$$$.