Background

Problem Description

This is an interactive problem.

You need to guess a hidden prime $p$. Each time, you may query an integer $a$, and the system will return the value of the Legendre symbol $\left(\frac{a}{p}\right)$, defined as follows:

• If $p \mid a$, return $0$.
• Otherwise, if there exists an integer $x$ such that $x^2 \equiv a \pmod{p}$, return $1$.
• Otherwise, return $-1$.

The Legendre symbol is a basic tool in number theory, and it satisfies Euler's criterion:

$$\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}$$

Interaction

Your program must interact with the judge through standard input and output. First, your program should start querying. Each query should be in the following format:

? a

Here, $a$ is an integer satisfying $1 \le a \le 10^6$. After each query, the judge will return an integer ($0$, $1$, or $-1$), and your program should read this value from standard input.

When you are sure about $p$, output the answer in the following format:

! p

Here, $p$ is the prime you guessed. After outputting the answer, your program must terminate immediately.

You may make at most $17$ queries. If the number of queries exceeds the limit, or the answer is wrong, or the format does not meet the requirements, the judge will consider it a wrong answer.

Note: After each output, you must flush the buffer, for example, use cout << endl or fflush(stdout) in C++, and print(..., flush=True) in Python.

You may ignore the running time of the interactive library.

1

-1

0

1

? 2

? 3

? 7

? 1

! 7

Hint

Sample Explanation #1

In the sample, the hidden prime is $p=7$. Explanation:

• Query $a=2$, and it returns $1$, because $3^2\equiv 2\pmod{7}$.
• Query $a=3$, and it returns $-1$, because $3$ is not a quadratic residue modulo $7$.
• Query $a=7$, and it returns $0$, because $7$ is divisible by $p$.
• Query $a=1$, and it returns $1$, because $1$ is always a quadratic residue.
• Finally, output the answer $7$.

Constraints

• $3 \le p \le 10^6$, and $p$ is prime.

Translated by ChatGPT 5