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.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5000$). The description of the test cases follows.

The first and only line of each test case contains one integer $n$ ($1 \le n \le 10^9$).

Interaction

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.