L. Darabona bel Interactive!!!
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is an interactive problem. Please read the Interaction section carefully.

After he resolved the conflict with Ahmad, Ammar went home and decided to create an interactive problem to add to this problemset. After a lot of thinking, Ammar decided to take a break so he could eat cookies and chat with his friends in their group "Richard Fan Club".

Ammar has $$$n \: (1 \leq n \leq 10^4)$$$ cookies, cookie $$$i$$$ is a circle with diameter $$$a_i \: (1 \leq a_i \leq 10^6)$$$. When Ammar eats a cookie, his happiness increases by its area. Ammar told his friends about the cookies he ate and his happiness. Later that night, Jamal (camel) opened the chat and started asking Ammar about the cookies, so Ammar decided to play the following game with him:

  • Jamal will ask Ammar the following question "$$$?$$$ $$$x$$$".
  • Ammar will respond with the number of cookies he ate that have two points on its circumference where the distance between them is exactly $$$x$$$.

Jamal has to find the value of Ammar's happiness after he ate all the cookies; can you help him ??

It can be proven that the happiness can be written as $$$\frac{Y \cdot \pi}{4}$$$ where $$$Y$$$ is an integer. You are asked to find $$$Y$$$.

Input

The first line contains a single integer $$$tc \: (1 \leq tc \leq 100)$$$ — the number of testcases. The description of the testcases follows.

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

Interaction

The first line of each testcase contains a single integer $$$n$$$. At this moment, the array $$$a$$$ is chosen. The interactor in this task is not adaptive. In other words, the array $$$a$$$ is fixed in every testcase and does not change during the interaction.

To ask a query, print the line of the following form (without quotes):

"$$$?$$$ $$$x$$$" $$$(1 \leq x \leq 10^9)$$$.

You can ask at most $$$21 \cdot n$$$ queries of this form.

If your query is not valid or you asked more than $$$21 \cdot n $$$ queries, the interactor will respond with $$$-1$$$. If this happens, your program must terminate immediately, and you will receive the Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After that, you receive an integer — Ammar's response to the query.

Next, if your program found Ammar's happiness, print a line with the following format(without quotes):

"$$$!$$$ $$$Y$$$"

Please read the statement to understand what $$$Y$$$ stands for.

Note that this line is not considered a query and is not taken into account when counting the number of queries asked.

The interactor will respond with $$$1$$$ if your answer is correct. Otherwise, it will respond with $$$0$$$. If this happens, your program must terminate immediately, and you will receive the Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After this, proceed to the next testcase.

If the interactor responded to a query with $$$-1$$$ or to the guess with $$$0$$$, your program must terminate immediately, and you will receive the Wrong Answer verdict. 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
  • stdout.flush() in Python
Example
Input
2
5
5
4
3
0
1
2
0
1
Output
? 1
? 3
? 4
? 5
! 58
? 2
! 2
Note

In the first testcase, $$$a=[1,3,4,4,4]$$$.

In the second testcase, $$$a=[1,1]$$$.