Note

This is an interactive problem.

It is also guaranteed that, with very high probability (specifically, $99$% or more), you can get AC with $1$ submission. Please refrain from repeated submissions, as they burden the judge.

Problem Statement

PCT-kun has a positive integer $X$ between $1$ and $N$, inclusive.

You can ask PCT-kun questions of the following form.

• Ask about a positive integer $Y$ between $1$ and $N$, inclusive. PCT-kun returns $\mathrm{GCD}(X,Y)$.

Guess the positive integer that PCT-kun has.

Input

$N$

• All inputs are integers.
• $1 \le N \le 10^4$

Input and Output

First, read the integer $N$ from standard input.

$N$

Next, the following shows how to send question queries and answer queries.

Question query

? Y

This query asks PCT-kun a question with the integer $Y$.

You can make this query at most $600$ times in total.

The response to this query is given on standard input as follows.

S

Here, S is one of the following.

• If the number of questions is $600$ or less, S is $\mathrm{GCD}(X,Y)$.
• If the number of questions is more than $600$, S is $-1$.

Answer query

! Z

This query outputs your guess of the integer that PCT-kun has. After outputting this query, terminate your program immediately.

Note

• Flush standard output after each output.
• Answer queries are not counted toward the number of question queries.
• If the above is not satisfied, the behavior of the judge is undefined.
• The judge for this problem may be adaptive. That is, the judge may change the integer that PCT-kun has, as long as it remains consistent with the responses so far.

Sample

5
3

? 3
! 3