E. Flatten or Concatenate
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is an interactive problem.

While procrastinating at work, Dilhan the elf stumbled upon two arrays $$$a$$$ and $$$b$$$. Initially, both of them consist of a single integer $$$2^k$$$ (i.e., $$$a=b=[2^k]$$$), where $$$k$$$ is a non-negative integer.

Dilhan then applied the following two types of operations an arbitrary number of times (possibly zero), in any order:

  1. Flatten — Choose either $$$a$$$ or $$$b$$$, and select any element $$$x$$$ that is maximal within that array ($$$x$$$ does not need to be maximal in the other array). Then, replace $$$x$$$ with two copies of $$$\frac x2$$$ in the same position. This operation can only be applied if $$$x$$$ is even.
  2. Concatenate — Set both $$$a$$$ and $$$b$$$ to be $$$a+b$$$, where $$$+$$$ denotes array concatenation.

After performing these operations, Dilhan discards $$$b$$$, hides $$$a$$$ from you, and challenges you to a game.

Let $$$n$$$ be the length of the hidden array $$$a$$$. You may make the following query:

  • Choose an interval $$$[l, r]$$$ ($$$1\le l\le r\le n$$$), and Dilhan will tell you the sum $$$a_l+a_{l+1}+\cdots+a_r$$$.

Determine the value of the maximum element of $$$a$$$ by making at most $$$300$$$ queries.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of $$$a$$$.

It is guaranteed that $$$1\le a_i\le 2^{30}$$$, and the array $$$a$$$ can be generated by the process described in the statements.

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

Interaction

For each test case, you are first given an integer $$$n$$$ — the length of the hidden array $$$a$$$. You may then make up to $$$300$$$ queries.

To make a query, print a line in the following format:

  • $$$\texttt{?}\;l\;r$$$ ($$$1\le l\le r\le n$$$) — the indices chosen for the query.

After you print a query, the interactor will respond with a single integer — the sum $$$a_l+a_{l+1}+\ldots+a_r$$$.

To report that you have determined the value of the maximum element of $$$a$$$, print your answer in the following format:

  • $$$\texttt{!}\; m$$$ ($$$1\le m\le 2^{30}$$$) — the value of the maximum element.

Printing the answer does not count as one of the $$$300$$$ queries.

After printing the answer, proceed to the next test case. If the current test case is the last one, terminate the program.

After printing each query do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict.

If, at any interaction step, you read $$$-1$$$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

The interactor in this problem is not adaptive. In other words, the array $$$a$$$ is fixed before any queries and will not change during the interaction.

Hacks are disabled in this problem.

$$$^{\text{∗}}$$$To flush, use:

  • fflush(stdout) or cout.flush() in C++;
  • sys.stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
4
11

9

4

12

1

1

8

4

4

4

4

8
Output


? 3 8

? 1 4

? 5 11

! 2

? 1 1

! 1

? 1 1

? 2 2

? 3 3

? 4 4

! 4

! 1073741824
Note

In the first test case, Dilhan's hidden array $$$a$$$ is $$$[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$$$. It can be generated by the following process:

#Type$$$a$$$ after operation$$$b$$$ after operation
0$$$[4]$$$$$$[4]$$$
1Flatten $$$a$$$$$$[\underline 4] \to {[2, 2]}$$$$$$[4]$$$
2Flatten $$$b$$$$$$[2, 2]$$$$$$[\underline 4] \to {[2, 2]}$$$
3Flatten $$$a$$$$$$[2, \underline 2] \to {[2, 1, 1]}$$$$$$[2, 2]$$$
4Concatenate$$$[2, 1, 1, 2, 2]$$$$$$[2, 1, 1, 2, 2]$$$
5Flatten $$$a$$$$$$[\underline 2, 1, 1, 2, 2]\to {[1, 1, 1, 1, 2, 2]}$$$$$$[2, 1, 1, 2, 2]$$$
6Concatenate$$$[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$$$$$$[1, 1, 1, 1, 2, 2, 2, 1, 1, 2, 2]$$$
  • For the query $$$\mathtt{?\;3\;8}$$$, the jury responded with $$$1+1+2+2+2+1=9$$$;
  • For the query $$$\mathtt{?\;1\;4}$$$, the jury responded with $$$1+1+1+1=4$$$;
  • For the query $$$\mathtt{?\;5\;11}$$$, the jury responded with $$$2+2+2+1+1+2+2=12$$$.

And the value of the maximum element of $$$a$$$ is $$$2$$$.

In the second test case, the array $$$a$$$ has only one element. By the query, the value of the only element is $$$1$$$, and it must also be the maximum value.

In the third test case, Dilhan's hidden array $$$a$$$ is $$$[4, 4, 4, 4, 4, 4, 4, 4]$$$. It can be generated by the following process:

#Type$$$a$$$ after operation$$$b$$$ after operation
0$$$[4]$$$$$$[4]$$$
1Concatenate$$$[4, 4]$$$$$$[4, 4]$$$
2Concatenate$$$[4, 4, 4, 4]$$$$$$[4, 4, 4, 4]$$$
3Concatenate$$$[4, 4, 4, 4, 4, 4, 4, 4]$$$$$$[4, 4, 4, 4, 4, 4, 4, 4]$$$

And the value of the maximum element of $$$a$$$ is $$$4$$$.

In the fourth test case, Dilhan's hidden array $$$a$$$ is $$$[2^{29}, 2^{29}, 2^{30}, 2^{29}, 2^{28}, 2^{28}, 2^{29}, 2^{29}]$$$.