这是一个交互式问题。

我们选择了一个介于 $1$ 到 $n$ 之间的整数 $m$。你的任务是猜出这个数，且你的查询次数不能超过该 $n$ 所需的必要次数。你的每一次查询都必须是一个十进制表示下不超过 $n$ 位的整数。对于查询 $x$，返回的答案是 $x \pmod m$。

输入格式

首先，你的程序将接收一个整数 $n$ ($1 \le n \le 10^6$)。

随后，你的程序将接收查询的答案。每个答案都是一个整数。

输出格式

你的程序可以通过格式 ? number 进行查询。当你认为已经猜出答案时，请输出 ! guess，然后立即终止程序。不要忘记输出换行符并刷新缓冲区。为此，你可以使用以下指令：

• C++: fflush(stdout);
• Java: System.out.flush();
• Python: stdout.flush();
• Pascal: flush(output);

样例

样例输入 1

2
1

样例输出 1

? 79
! 2

样例输入 2

3
0
0
0

样例输出 2

? 42
? 777
? 8
! 1

说明

题目并不禁止输出前导零，但检查程序在确定数字长度时会计算这些前导零。例如，如果 $n = 3$，查询 “001” 是合法的，但 “0001” 是非法的。

第二个样例仅用于演示交互格式，实际上可以用更少的查询次数猜出答案。