H. Holy Division
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
This is an interactive problem.
Make sure to flush the output after each query, or your program's verdict will be judged as Time Limit Exceeded. This works in various languages:
  • Java: System.out.println() flushes automatically.
  • Python: print(..., flush = True) flushes.
  • C++: cout « endl; flushes automatically, in addition to writing a newline. If using printf, use fflush(stdout).

Apollo, the god of prophecy, has hidden an integer $$$n$$$ ($$$1\leq n\leq 10^8$$$). Mortals are not allowed to know $$$n$$$ directly, but Apollo may answer queries and perform divisions for you.

One of Apollo's prophecies states that an integer $$$x$$$ is sacred if and only if $$$x$$$ has at most $$$8$$$ positive divisors.

Although mortals do not know Apollo's value of $$$n$$$, Apollo believes you are no mere mortal. Prove your worthiness by reducing $$$n$$$ to a sacred value $$$n'$$$ (where $$$n' \leq n$$$).

Interaction

For the purposes of this interaction, the jury acts on Apollo's behalf.

The interaction begins when you ask your first query. On your turn, you can make one of three types of queries:

  • gcd d ($$$1\leq d \leq 10^{18}$$$) followed by a newline. The jury then returns $$$\gcd(n, d)$$$. The value of $$$n$$$ is unchanged by this query.
  • div d ($$$1\leq d \leq 10^{18}$$$) followed by a newline. If $$$d$$$ divides $$$n$$$, the jury replaces $$$n$$$ with $$$n/d$$$ and returns 1; otherwise $$$n$$$ is unchanged and the jury returns 0.
  • ! followed by a newline. This declares that the current value of $$$n$$$ is sacred. Your program should terminate immediately after this.
You may ask a combined total of $$$7$$$ queries of gcd d and div d.

In the event that you read -1 instead of valid data, your program must terminate immediately. This indicates that your submission has made an invalid query or has otherwise received a Wrong Answer verdict.

Example
Input

0 # reply 1

1 # reply 2

1 # reply 3

16 # reply 4
Output
div 3 # query 1

div 4 # query 2

div 4 # query 3

gcd 16 # query 4

! # answer
Note

The following sample interaction is meant to showcase the interaction between your program and the jury, but does not show how the answer was derived. Note that comments (marked by #) are there for readability and are not part of the actual interaction.

Apollo's integer was initially $$$n = 256$$$. The sample makes a total of $$$4$$$ out of $$$7$$$ queries.

  • The first query attempts to divide $$$n$$$ by $$$3$$$. Since $$$3$$$ is not a divisor of $$$n=256$$$, $$$n$$$ remains unchanged and the jury outputs 0.
  • The second query attempts to divide $$$n$$$ by $$$4$$$. Since $$$4$$$ is a divisor of $$$n=256$$$, $$$n \leftarrow 256/4 = 64$$$. After this query $$$n = 64$$$, and the jury outputs 1.
  • The third query attempts to divide $$$n$$$ by $$$4$$$. Since $$$4$$$ is a divisor of $$$n = 64$$$, $$$n \leftarrow 64/4 = 16$$$. After this query $$$n = 16$$$, and the jury outputs 1.
  • The fourth query asks for $$$\gcd(n, 16)$$$. The jury outputs $$$16$$$.
Finally, the interaction concludes with ! because $$$16$$$ has $$$5$$$ positive divisors (the positive divisors of 16 are $$$[1,2,4,8,16]$$$), which is sacred.