시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2.5 초 512 MB 18 1 1 100.000%

## 문제

We have chosen an integer $m$ between $1$ and $n$. Your task is to guess it, and you have to do no more queries than necessary for this $n$. Each of your queries must be an integer which has no more than $n$ digits in its decimal notation. The answer to query $x$ is the remainder $x \bmod m$.

## 입력

In the beginning, your program will receive one integer $n$ ($1 \le n \le 10^6$).

## 출력

Your program can make queries in the form "? $\mathit{number}$". When you think you know the answer, you should print "! $\mathit{guess}$", and then terminate your program immediately. Don't forget to output the line break and flush the output. To do so, you can use the following instructions:

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

## 예제 입력 1

2
1


## 예제 출력 1

? 79
! 2


## 예제 입력 2

3
0
0
0


## 예제 출력 2

? 42
? 777
? 8
! 1


## 힌트

You are not prohibited to output leading zeroes, but the checking program counts them when determining the length of the number. For example, if $n = 3$, query "$001$" is valid, but "$0001$" is invalid.

The second sample just demonstrates the interaction format, guessing can be done in smaller number of queries.

## 채점

• 예제는 채점하지 않는다.