This is the easy version of the problem. In this version, you can send at most $\mathbf{7}$ 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:

CommandConstraintResultCaseUpdate****Jury's response"add $y$"$-10^{18} \le y \le 10^{18}$$\mathrm{res} = x + y$$\text{if } 1 \le \mathrm{res} \le 10^{18}$$x \leftarrow \mathrm{res}$%%ACcode1%%$\mathrm{else}$$x \leftarrow x$"0""mul $y$"$1 \le y \le 10^{18}$$\mathrm{res} = x \cdot y$$\text{if } 1 \le \mathrm{res} \le 10^{18}$$x \leftarrow \mathrm{res}$%%ACcode4%%$\mathrm{else}$$x \leftarrow x$"0""div $y$"$1 \le y \le 10^{18}$$\mathrm{res} = x/y$$\text{if } y$ divides $x$$x \leftarrow \mathrm{res}$%%ACcode7%%$\mathrm{else}$$x \leftarrow x$"0""digit"—$\mathrm{res} = S(x)$$^{\text{∗}}$—$x \leftarrow \mathrm{res}$"1"

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

$^{\text{∗}}$$S(n)$ is a function that returns the sum of all the individual digits of a non-negative integer $n$. For example, $S(123) = 1 + 2 + 3 = 6$

Input

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{7}$ commands.

If your program makes more than $\mathbf{7}$ 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.

Note

SolutionJuryExplanation$\texttt{2}$There are 2 test cases.$\texttt{100}$In the first test case, the unknown integer $x = 9$ and we have to make it equal to $n = 100$.$\texttt{add -10}$$\texttt{0}$The answer to %%ACcode0%% is %%ACcode1%%. This means that the addition command was not successful as $x + y = 9 + (-10) \le 0$, and $x$ remains $9$ after the command$\texttt{add 1}$$\texttt{1}$The answer to "add 1" is "1". This means that the addition command was successful as $x + y = 9 + 1 = 10$, and $x$ changes to $10$ after the command.$\texttt{mul 10}$$\texttt{1}$The answer to %%ACcode4%% is %%ACcode5%%. This means that the multiplication command was successful as $x \cdot y = 10 \cdot 10 = 100$, and $x$ changes to $100$ after the command.$\texttt{!}$$\texttt{1}$The answer to "!" is "1". This means you have determined that $x$ equals $n$.$\texttt{5}$In the second test case, the unknown integer $x = 1234$ and we have to make it equal to $n = 5$.$\texttt{digit}$$\texttt{1}$The answer to %%ACcode8%% is %%ACcode9%%. This means that $x$ turned into the sum of its digits $1 + 2 + 3 + 4 = 10$, and $x$ changes to $10$ after the command.$\texttt{div 2}$$\texttt{1}$The answer to "div 2" is "1". This means that the division command was successful as $y = 2$ is a divisor of $x = 10$, and $x$ changes to $\frac{x}{y} = \frac{10}{2} = 5$ after the command.$\texttt{!}$$\texttt{1}$The answer to "!" is "1". This means you have determined that $x$ equals $n$.

Note that the empty lines in the example input and output are for the sake of clarity, and do not occur in the real interaction.