Game of Guessing Her Password!
This is an interactive problem.
Like everyone, Nubu the random coder girl, has a secret password. One day some of her friends wanted to guess her password. They call it a guessing game! To make the guessing game more interesting, she reveals them that the password is an integer number between $1$ and $10^3$. Let’s say, her secret password is $n$. Her friends can tell her a positive integer number, $m$. In return, she will tell them the value of $gcd(n, m)$. But the friends can not ask more than $Q$ times. The friends can not figure out how they can do it. So they have come to you!
Input
The first line will contain the number of test cases $T$ ($1 \leq T \leq 1000$).
Interaction Details
For each test case, to ask a question, print "? m" (without quotes) in a line, where $1 \leq m \leq 10^9$. Then, you should read a single integer. The integer will denote the $gcd(n, m)$.
If you think you have found the password $n$ then, print "! n" (without quotes) in a line. After that, continue to the next test case (do not need to take any input). If you pass every test case correctly, then you will get "Accepted", otherwise "Wrong Answer" verdict.
You can ask at most $Q$ questions (excluding printing answer). If you exceed the number of questions or ask any invalid question, you will receive $-1$ as the answer of your question.
At any point, terminate your program immediately after receiving $−1$ and you will see Wrong answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.
Constraints
Subtask 1 (up to 10 Points)
$1 \leq T \leq 50$$1 \leq Q \leq 999$
Subtask 2 (up to 30 Points)
$1 \leq Q \leq 168$
Subtask 3 (up to 60 Points)
$1 \leq Q \leq 56$
Output
If we assume the secret number is 15 then interaction may look like:
> 1
< ? 5
> 5
< ? 3
> 3
< ? 15
> 15
< ? 30
> 15
< ! 15
> indicates what your program reads and < indicates what your program writes. These symbols are here to make it easy to understand. You do not have to print such symbols from your program.
Notes
To learn more about Interactive Problems: https://help.toph.co/toph/interactive-problems