Heidi 正在分析一个特殊的设备。该设备以 $a$ 作为输入，并使用以下伪代码以及存储在设备中的整数 $d$ 和 $n$ 来计算 $a^d \pmod n$：

modPow(a, d, n) {
    r = 1;
    for (i = 0; i < 60; ++i) {
        if ((d & (1 << i)) != 0) {
            r = r * a % n;
        }
        a = a * a % n;
    }
}

注意，上述伪代码假设使用任意大小的整数，<< 表示按位左移，& 表示按位与，% 表示取模。

该设备不会告诉 Heidi 计算结果。然而，Heidi 可以测量计算所花费的时间。她知道只有模 $n$ 的乘法（上述伪代码中的第 5 行和第 7 行）会消耗可测量的时间，其他所有行均可视为耗时 0 纳秒。此外，她知道将 $x$ 与 $y$ 进行模 $n$ 乘法运算需要 $(bits(x) + 1) \cdot (bits(y) + 1)$ 纳秒，其中 $bits(x)$ 是 $x$ 二进制表示中不含前导零的位数，或者更正式地定义为 $bits(x) = \lfloor \log_2(x + 1) \rfloor$。

Heidi 知道整数 $n$，但不知道整数 $d$。她希望通过向设备输入不同的整数 $a$ 并测量每次计算所花费的时间来找出 $d$。

她知道 $n$ 和 $d$ 是按以下方式选择的：首先，独立且均匀随机地选取两个二进制表示为 30 位的质数 $p$ 和 $q$（换句话说，在 $2^{29}$ 和 $2^{30} - 1$ 之间）。然后计算 $n = p \cdot q$。接着计算 $m = \phi(n) = (p - 1) \cdot (q - 1)$。最后，在 $1$ 到 $m - 1$（包含边界）之间均匀随机选取一个与 $m$ 互质的整数 $d$。

交互

首先，测试系统会写入整数 $n$ —— 设备所使用的模数。注意，$n$ 和隐藏的整数 $d$ 保证是按照上述过程生成的。

你的程序需要输出两种类型的请求：

• “? a” 表示将 $a$ 作为输入发送给设备。$a$ 必须是 $0$ 到 $n - 1$ 之间的整数。测试系统将返回设备计算 modPow(a, d, n) 所花费的时间（单位为纳秒）。
• “! d” 表示你程序确定的 $d$ 的值。

每次请求后请务必刷新输出！

你的程序必须恰好发出一次第二种类型的请求，且该请求必须是最后一次请求，程序在发出该请求后必须正常终止。

你的程序最多允许发出 30,000 次第一种类型的请求。

你的程序将在 30 个测试用例上运行，每个测试用例对应一对 $(n, d)$。对于每个测试用例，$n$ 和 $d$ 都是固定的，并使用上述过程生成。下方的样例并非按此方式生成，因此不会用于测试你的程序；它仅用于说明输入/输出格式并提供对计算时间计算的验证。

样例

输入 1

15
980
293

输出 1

? 3
? 8
! 5

说明

在样例的第一次请求中，设备在计算 modPow(3, 5, 15) 时执行了以下乘法：

• $1 \cdot 3 \pmod{15} = 3$，耗时 6 纳秒
• $3 \cdot 3 \pmod{15} = 9$，耗时 9 纳秒
• $9 \cdot 9 \pmod{15} = 6$，耗时 25 纳秒
• $3 \cdot 6 \pmod{15} = 3$，耗时 12 纳秒
• $6 \cdot 6 \pmod{15} = 6$，耗时 16 纳秒
• $6 \cdot 6 \pmod{15} = 6$，耗时 16 纳秒
• $6 \cdot 6 \pmod{15} = 6$，耗时 16 纳秒
• ...（最后一次乘法重复了 55 次）

计算总耗时为 $6 + 9 + 25 + 12 + 58 \cdot 16 = 980$ 纳秒。

如果一个正整数恰好有两个约数：1 和它本身，则称其为质数。如果两个正整数的最大公约数为 1，则称它们互质。

以下是函数 $bits(x)$ 的前几个值：

• $bits(0) = 0$
• $bits(1) = 1$
• $bits(2) = 2$
• $bits(3) = 2$
• $bits(4) = 3$
• ...