背景

题目描述

这是一道交互题。

你需要猜测一个隐藏的素数 $p$。每次你可以询问一个整数 $a$，系统将返回勒让德符号 $\left(\frac{a}{p}\right)$ 的值，定义如下：

• 如果 $p \mid a$，返回 $0$；
• 否则，如果存在整数 $x$ 使得 $x^2 \equiv a \pmod{p}$，返回 $1$；
• 否则，返回 $-1$。

勒让德符号是数论中的基本工具，它满足欧拉准则：

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

交互方式

你的程序需要通过标准输入输出与评测系统交互。首先，程序应开始询问，每次询问格式为：

? a

其中 $a$ 是一个整数，满足 $1 \le a \le 10^6$。每次询问后，评测系统会返回一个整数（$0$、$1$ 或 $-1$），你的程序应从标准输入读取该返回值。

当你确定 $p$ 后，应输出答案，格式为：

! p

其中 $p$ 是你猜测的素数。输出答案后，你的程序应立即结束。

你最多可以进行 不超过 $17$ 次询问。如果询问次数超过限制，或者答案错误，或者格式不符合要求，评测系统将判定为错误答案。

注意：每次输出后必须刷新缓冲区，例如 C++ 中使用 cout << endl 或 fflush(stdout)，Python 中使用 print(..., flush=True)。

你可以忽略交互库的运行时间。

1

-1

0

1

? 2

? 3

? 7

? 1

! 7

提示

【样例解释 #1】

样例中隐藏的素数为 $p=7$。解释：

• 询问 $a=2$，返回 $1$，因为 $3^2\equiv 2\pmod{7}$。
• 询问 $a=3$，返回 $-1$，因为 $3$ 不是模 $7$ 的二次剩余。
• 询问 $a=7$，返回 $0$，因为 $7$ 被 $p$ 整除。
• 询问 $a=1$，返回 $1$，因为 $1$ 总是二次剩余。
• 最后输出答案 $7$。

【数据范围】

• $3 \le p \le 10^6$，$p$ 为素数。