Practice on Toph

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

Game of Guessing Her Password!

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 11 and 10310^3. Let’s say, her secret password is nn. Her friends can tell her a positive integer number, mm. In return, she will tell them the value of gcd(n,m)gcd(n, m). But the friends can not ask more than QQ 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 TT (1T10001 \leq T \leq 1000).

Interaction Details
For each test case, to ask a question, print "? m" (without quotes) in a line, where 1m1091 \leq m \leq 10^9. Then, you should read a single integer. The integer will denote the gcd(n,m)gcd(n, m).

If you think you have found the password nn 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 QQ questions (excluding printing answer). If you exceed the number of questions or ask any invalid question, you will receive 1-1 as the answer of your question.

At any point, terminate your program immediately after receiving 1−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)

1T501 \leq T \leq 50
1Q9991 \leq Q \leq 999

Subtask 2 (up to 30 Points)

1Q1681 \leq Q \leq 168

Subtask 3 (up to 60 Points)

1Q561 \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

    Discussion

    Statistics


    54% Solution Ratio

    Samin_SieyamEarliest, Jun '20

    SIR.24Fastest, 0.1s

    Samin_SieyamLightest, 131 kB

    Jarif_RahmanShortest, 597B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.