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:

Command	Constraint	Result	Case	Update	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}$$$	"1"
"add $$$y$$$"	$$$-10^{18} \le y \le 10^{18}$$$	$$$\mathrm{res} = x + y$$$	$$$\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}$$$	"1"
"mul $$$y$$$"	$$$1 \le y \le 10^{18}$$$	$$$\mathrm{res} = x \cdot y$$$	$$$\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}$$$	"1"
"div $$$y$$$"	$$$1 \le y \le 10^{18}$$$	$$$\mathrm{res} = x/y$$$	$$$\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{4}$$$ 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{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.

Note

Solution	Jury	Explanation
	$$$\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 "add -10" is "0". 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 "mul 10" is "1". 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 "digit" is "1". 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.

Hacking Numbers (Medium Version)

Examples