注意

この問題は、インタラクティブ形式の問題です。

また、非常に高い確率(具体的には $99$% 以上)で $1$ 回の提出で AC できることが保証されています。ジャッジの負担となるため、連投はお控えください。

問題文

PCT 君は $1$ 以上 $N$ 以下のある正整数 $X$ を持っています。

あなたは以下の形式の質問を PCT 君にすることができます。

• $1$ 以上 $N$ 以下のある正整数 $Y$ を聞く。PCT 君からは、$\mathrm{GCD}(X,Y)$ が返ってくる。

PCT 君の持っている正整数を当ててください。

入力

$N$

• 入力は全て整数である。
• $1 \le N \le 10^4$

入出力

最初に、整数 $N$ を標準入力から受け取ってください。

$N$

次に、質問クエリと回答クエリの送信方法を示します。

質問クエリ

? Y

PCT 君に整数 $Y$ で質問することを示すクエリです。

このクエリは合計 $600$ 回までしか行うことができません。

このクエリに対する解答は、以下のように標準入力に与えられます。

S

ここで、S とは以下のうちいずれかです。

• 質問回数が $600$ 回以下の時、S は $\mathrm{GCD}(X,Y)$ です。
• 質問回数が $600$ 回より多い場合、S は $-1$ です。

解答クエリ

! Z

PCT 君の持っている整数とあなたが予想したものを出力するクエリです。このクエリが出力された後、プログラムを直ちに終了してください。

注意

• 出力のあと、標準出力を flush してください。
• 解答クエリは、質問クエリの回数に含めません。
• 上記を満たさない場合、ジャッジの挙動は不定です。
• この問題のジャッジは適応的である可能性があります。つまり、ジャッジは今までの返答と整合性が取れる限り、PCT 君の持っている整数を変更する可能性があります。

サンプル

5
3

? 3
! 3