L. Fyreflies
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

You're invited by Firefly to a garden, where $$$10^5$$$ trees are lined up. The trees are numbered from $$$1$$$ to $$$10^5$$$ from left to right. She tells you she has put $$$n$$$ groups of fyreflies, each group located at a distinct secret tree $$$x_i$$$, and she would like to play a game with you. You can query a coordinate $$$x$$$, and Firefly will tell you the sum of the Manhattan distance$$$^{\text{∗}}$$$ between your guess and each group's coordinates.

However, there is little time for Firefly to spend with you, and you have to come up with one of the groups' coordinates within $$$40$$$ queries. If you manage to do so, she can take you to the coordinate and enjoy the fyreflies with you. If you fail, she will have to say farewell and carry out her mission.

$$$^{\text{∗}}$$$The Manhattan distance between two coordinates $$$x_1$$$ and $$$x_2$$$ is given by $$$|x_1-x_2|.$$$

Input

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

The first line contains one integer $$$n$$$ ($$$1\le n\le10^4$$$) — the number of fyrefly groups.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^4$$$.

Interaction

To make a query, output a line in the following format (do not include quotes):

"$$$\mathtt{?}$$$ $$$x$$$" ($$$1\le x\le 10^5$$$)

Here, $$$x$$$ represents your query coordinate.

After each query, you should read a line containing one integer, indicating the sum of the Manhattan distance between your guess and each group's coordinates. In other words, the integer is $$$\displaystyle{\sum_{i=1}^{n}|x_i-x|}$$$.

When you are ready to print the answer, output a single line in the following format:

"$$$\mathtt{!}$$$ $$$x$$$" ($$$1\le x\le 10^5$$$)

Here, $$$x$$$ represents your answer coordinate.

You can make at most $$$40$$$ 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 $$$40$$$ 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 may get Idleness limit exceeded verdict. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • Console.Out.Flush() in C#;
  • stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
2
7

34

25

4
Output


? 12

? 5

! 1

! 42657
Note

In the first sample case, $$$x=[13,5,10,8,9,6,1]$$$.

In the second sample case, $$$x=[85688,42657,37978,85893]$$$.