406317: GYM102354 I From Modular to Rational

I. From Modular to Rationaltime limit per test6 secondsmemory limit per test256 mebibytesinputstandard inputoutputstandard output

This is an interactive problem.

Someone picked a positive rational number $$$x=p/q$$$ where $$$1 \leq p, q \leq 10^9$$$. You may ask at most $$$10$$$ queries of the kind "? $$$m$$$", where $$$10^9 < m < 10^{12}$$$ and $$$m$$$ is a prime number. For each query, you will get the number $$$y$$$ such that $$$y \equiv pq^{-1} \pmod{m}$$$. You have to guess the number $$$x$$$.

Interaction

The first line of input contains a single integer $$$t$$$, the number of test cases ($$$1 \leq t \leq 10^5$$$).

For each test case, you may ask at most $$$10$$$ queries. Each query should be one of two types:

1. "? $$$m$$$", where $$$10^9 < m < 10^{12}$$$ and $$$m$$$ is a prime number,
2. "! $$$p$$$ $$$q$$$", where $$$1 \leq p, q \leq 10^9$$$, meaning that the answer is equal to $$$p/q$$$.

It is guaranteed that the number $$$x$$$ in each test case does not change during testing.ExampleInput

3

1


500000004


2

Output

 
? 1000000007

! 1 1
? 1000000007

! 2 4
? 1000000007

! 2 1

Note

In the example, you deal with $$$x=1/1$$$, $$$x=1/2$$$, and $$$x=2/1$$$, while always taking $$$m=10^9+7$$$.

As you may see, it is not necessary to have $$$\gcd(p,q)=1$$$ as long as $$$1\leq p,q\leq 10^9$$$ and $$$x=p/q$$$.