Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

By ovis96 · Limits 2s, 512 MB · Interactive

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.

Since this is an interactive problem, don’t forget to flush your output after printing each line. You may use fflush(stdout) for printf or cout << flush for cout in C++, system.out.flush() in Java, stdout.flush() in Python to flush the output. If you use some other programming language, consult its documentation.

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.

Statistics

52% Solution Ratio

Samin_SieyamEarliest, 1M ago

SIR.24Fastest, 0.1s

Samin_SieyamLightest, 131 kB

Jarif_RahmanShortest, 597B