A. GCD,LCM and AVG
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

Chromate has a secret positive integer $$$x$$$ ($$$1 \le x \le 10^9$$$), and wants you to guess it.

Formally, you can ask him about some positive integer $$$a$$$, and Chromate will return the value of $$$\lfloor \frac{ gcd(a,x) + lcm(a,x)}{2} \rfloor$$$ to you.

Here $$$gcd(a,x)$$$ means the greatest common divisor of $$$a$$$ and $$$x$$$, while $$$lcm(a,x)$$$ means the least common multiple of $$$a$$$ and $$$x$$$.$$$\lfloor \rfloor$$$ is the rounding symbol for downward rounding.

You must find out the value of the integer $$$x$$$ within $$$4$$$ queries. The number of queries includes the final query where $$$x=a$$$.

Before any interaction begins, you are given $$$t$$$($$$1 \le t \le 10^4$$$), the number of test cases.

During the interaction, you may ask about the integer $$$a(1 \le a \le 10^9)$$$ by "? a". The interactor will give you the integer $$$\lfloor \frac{ gcd(a,x) + lcm(a,x)}{2} \rfloor$$$(note it may be greater than $$$10^9$$$).

When your program guessed the number $$$x$$$, print string "! x", where $$$x$$$ is the answer.

Note:after printing a query do not forget to output end of line and flush the output.

To do this, use:

  1. fflush(stdout) or cout.flush() in C++;
  2. System.out.flush() in Java;
  3. flush(output) in Pascal;
  4. stdout.flush() in Python.
Input

Use standard input to read the responses to the queries.

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test data.

Following lines will contain responses to your queries — the value of $$$\lfloor \frac{ gcd(a,x) + lcm(a,x)}{2} \rfloor$$$. The $$$i$$$-th line is a response to your $$$i$$$-th query. When your program will guess the number print "! x", where $$$x$$$ is the answer and terminate your program.

The testing system will allow you to read the response on the query only after your program print the query for the system and perform flush operation.

Output

To make the queries your program must use standard output.

Your program must print the queries — "? a", one query per line (do not forget "end of line" after each query). After printing each line your program must perform operation flush.

The response to the query will be given in the input file after you flush output. In case your program guessed the number $$$x$$$, print string "! x", where $$$x$$$ — is the answer.

Example
Input
2

500000002

3

2

5001

51

4
Output

? 1000000000

? 4

? 2

! 2

? 9999

? 99

? 6

! 3