这是一个交互式问题。

毫无疑问，阿尔伯特·爱因斯坦为现代物理学做出了巨大贡献。然而，也有一些有趣的轶事归于他名下。例如，爱因斯坦的五间房谜题：这是一个谜题，你被告知诸如“英国人住在红房子里”或“抽 Pall Mall 香烟的人养鸟”之类的信息，你需要确定谁住在哪个房子里。有传言说，有一次爱因斯坦的朋友们找不到他的房子在哪里，因为他用一个谜题告诉了他们他的地址！他的朋友们进行了猜测：“我认为你住在第 $x$ 号房子里”，爱因斯坦回答说：“你说对了！”或者“你说错了，恰好有 $k$ 个朋友的猜测比你的猜测更接近我的房子”。幸运的是，现在你不需要解决任何谜题，可以去参观位于伯尔尼 Kramgasse 49 号的爱因斯坦博物馆。

但如果你想练习猜测，我们可以提供帮助。评测系统选择了一个 $1$ 到 $n$ 之间的奇数，你需要猜出它。你可以提交偶数作为查询，对于每次查询，你将收到在你之前的查询中，比最后一次查询更接近所选数字的查询数量。你的任务是通过提交一个奇数作为猜测来最终猜出所选数字。

你最多可以进行 7 次提交，包括最后的猜测。

交互

你将在一个测试中进行多场游戏（测试用例），数量从 1 到 100。当一个新的测试用例开始时，你会得到一行包含一个整数 $n$ ($1 \leqslant n \leqslant 100$，$n$ 为偶数)。如果 $n = 0$，你的程序必须立即退出。

要进行查询，请打印一行 “? $x$”，其中 $x$ 是一个偶数 ($0 \leqslant x \leqslant n$)。对每次查询的响应将是单独一行上的一个整数：在你之前的查询中，比最后一次查询更接近所选数字的查询数量。

要进行猜测，请打印一行 “! $y$”，其中 $y$ 是一个奇数 ($0 \leqslant y \leqslant n$)。如果你猜对了，评估将继续进行下一个测试用例。否则，它将以 “Wrong Answer” 的结果终止。

解决单个测试用例所打印的总行数不能超过 7 行。如果你打印的行数超过此限制，评估将以 “Wrong Answer” 的结果终止。

请记住在打印每一行后刷新输出。否则，你的解决方案很可能会以 “Idleness Limit Exceeded” 的结果终止。

在每个测试的每个测试用例中，你必须猜测的数字是固定的，并且每次评估你的解决方案时，该数字在同一个测试用例上都是相同的。

样例

输入 1

2
6
0
1
1
0

输出 1

! 1
? 2
? 6
? 0
! 3