G. Contrived Intelligence
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

This is an interactive problem.

With the field of artificial intelligence on the rise, you have decided to take a detour and instead look at the human mind again. You have realized that the emotions of your best friend, Adamant, can be encoded as a hidden polynomial with integer coefficients; call it $$$P(x)$$$. To know more about $$$P(x)$$$, you can ask everyday questions from Adamant while obtaining mathematical values related to $$$P(x)$$$ from his answers.

There are $$$N$$$ questions that you may ask, numbered $$$1$$$ through $$$N$$$. Whenever you ask the $$$k$$$-th question, you are told how many of the integers $$$P(1), P(2), \dots, P(k)$$$ are divisible by $$$k$$$.

Of course, it is impossible to fully understand a person simply from talking to them, but you would like to predict how Adamant might behave in certain scenarios.

There are $$$N$$$ possible scenarios, numbered $$$1$$$ through $$$N$$$. In the $$$k$$$-th scenario, Adamant's behavior is fully determined by the number of integers among $$$P(1), P(2), \dots, P(k)$$$, which are co-prime with $$$k$$$.

You have to predict Adamant's behavior in each scenario while asking him at most $$$10^4$$$ questions.

Interaction

The interaction begins with the interactor providing you with the number $$$N$$$ ($$$1 \leq N \leq 10^5$$$), which serves as the upper limit on the questions and the number of scenarios. You can then begin asking questions.

To ask the $$$k$$$-th question ($$$1 \leq k \leq N$$$), print "? k", without quotes. Afterward, you should read a single integer, the answer to the $$$k$$$-th question. Don't forget to flush the output after printing a question!

You are only allowed to ask at most $$$10^4$$$ questions.

When you have fully determined Adamant's behavior in all possible scenarios, print "! ", followed by $$$N$$$ integers. The $$$k$$$-th integer must be the number of integers $$$j$$$, such that $$$1 \leq j \leq k$$$ and $$$\gcd(P(j), k) = 1$$$.

For each test, the polynomial $$$P(x)$$$ is chosen in advance and does not change.

Examples
Input
3

1

0
Output

? 2

? 3

! 1 1 3
Input
6

1

1

0
Output

? 1

? 5

? 6

! 1 1 3 2 4 3
Note

In the first sample, the polynomial is $$$P(x) = x^2+1$$$. In the first query, the answer is $$$1$$$, as among $$$1^2+1$$$ and $$$2^2+1$$$, exactly one is divisible by $$$2$$$.

In the second example, the hidden polynomial $$$P(x)$$$ is $$$3x^3+2$$$.

To flush the output, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see the documentation for other languages.