시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
20 초 256 MB 7 2 2 66.667%

문제

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$.

프로토콜

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:

  • "? $m$", where $10^9 < m < 10^{12}$ and $m$ is a prime number,
  • "! $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.

예제 입력 1

3

1


500000004


2

예제 출력 1

? 1000000007

! 1 1
? 1000000007

! 2 4
? 1000000007

! 2 1

힌트

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$.

채점

  • 예제는 채점하지 않는다.