This is the medium version of the problem. In this version, you can send at most $$$\mathbf{4}$$$ commands. You can make hacks only if all versions of the problem are solved.

This is an interactive problem.

Welcome, Duelists! In this interactive challenge, there is an unknown integer $$$x$$$ ($$$1 \le x \le 10^9$$$). You must make it equal to a given integer in the input $$$n$$$. By harnessing the power of "Mathmech" monsters, you can send a command to do one of the following:

You have to make $$$x$$$ equal to $$$n$$$ using at most $$$\mathbf{4}$$$ commands.

The interaction for each test case begins by reading the integer $$$n$$$.

To send a command, output a line in the following format:

• "add $$$y$$$" Add some integer $$$y$$$ ($$$-10^{18} \le y \le 10^{18}$$$) to $$$x$$$.

  The jury will output "1" if $$$x + y$$$ is within $$$[1, 10^{18}]$$$ (successful), and "0" otherwise. If successful, update $$$x \leftarrow x + y$$$.

• "mul $$$y$$$" Multiply $$$x$$$ by a positive integer $$$y$$$ ($$$1 \le y \le 10^{18}$$$).

  The jury will output "1" if $$$x \cdot y$$$ is within $$$[1, 10^{18}]$$$ (successful), and "0" otherwise. If successful, update $$$x \leftarrow x \cdot y$$$.

• "div $$$y$$$" Divide $$$x$$$ by a positive integer $$$y$$$ ($$$1 \le y \le 10^{18}$$$).

  The jury will output "1" if $$$y$$$ is a divisor of $$$x$$$ (successful), and "0" otherwise. If successful, update $$$x \leftarrow \frac{x}{y}$$$.

• "digit" Make $$$x$$$ equal to the sum of its digits.

  The jury will always output "1" and update $$$x \leftarrow S(x)$$$.

Note that commands are case sensitive.

When you have determined that $$$x$$$ is equal to $$$n$$$, output a line in the following format:

• "!" — where the jury will output a "1" if $$$n$$$ is equal to $$$x$$$, and "-1" otherwise.

Note that answering does not count toward your limit of $$$\mathbf{4}$$$ commands.

If your program makes more than $$$\mathbf{4}$$$ commands for one test case, or makes an invalid command, then the response to the command will be "-1". After receiving such a response, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, it may receive any other verdict.

After printing a command, do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• sys.stdout.flush() in Python;
• std::io::stdout().flush() in Rust;
• see the documentation for other languages.

The interactor is non-adaptive. The unknown integer $$$x$$$ does not change during the interaction.

Hacks

To hack, use the following format.

The first line should contain a single integer $$$t$$$ ($$$1 \leq t \leq 5000$$$) — the number of test cases.

The first line of each test case should contain two positive integers $$$n$$$ and $$$x$$$ ($$$1 \leq n,x \leq 10^9$$$) — denoting the unknown integer and the target value to which it should be made equal, respectively.