This is an interactive problem.

Kira has a hidden positive integer $n$, and Hayato needs to guess it.

Initially, Kira gives Hayato the value $\mathrm{cnt}$ — the number of unit bits in the binary notation of $n$. To guess $n$, Hayato can only do operations of one kind: choose an integer $x$ and subtract it from $n$. Note that after each operation, the number $n$ changes. Kira doesn't like bad requests, so if Hayato tries to subtract a number $x$ greater than $n$, he will lose to Kira. After each operation, Kira gives Hayato the updated value $\mathrm{cnt}$ — the number of unit bits in the binary notation of the updated value of $n$.

Kira doesn't have much patience, so Hayato must guess the original value of $n$ after no more than $30$ operations.

Since Hayato is in elementary school, he asks for your help. Write a program that guesses the number $n$. Kira is an honest person, so he chooses the initial number $n$ before all operations and does not change it afterward.

Input

The input data contains several test cases. The first line contains one integer $t$ ($1 \le t \le 500$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains the number $\mathrm{cnt}$ — the initial number of unit bits in the binary notation $n$.

The hidden integer $n$ satisfies the following constraint: $1 \le n \le 10^9$.

Interaction

To guess $n$, you can perform the operation at most $30$ times. To do that, print a line with the following format: "- x" ($1 \le x \le 10^9$).

After this operation, the number $x$ is subtracted from $n$, and therefore $n$ is changed. If the number $x$ is greater than the current value of $n$, then the request is considered invalid.

After the operation read a line containing a single non-negative integer $\mathrm{cnt}$ — the number of unit bits in the binary notation of the current $n$ after the operation.

When you know the initial value of $n$, print one line in the following format: "! n" ($1 \le n \le 10^9$).

After that, move on to the next test case, or terminate the program if there are none.

If your program performs more than $30$ operations for one test case, subtracts a number $x$ greater than $n$, or makes an incorrect request, then response to the request will be -1, after receiving such response, your program must exit immediately to receive the Wrong Answer verdict. Otherwise, you can get any other verdict.

After printing a query or the answer, do not forget to output the end of 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;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

Hacks

To make a hack, use the following format.

The first line should contain a single integer $t$ ($1 \leq t \leq 500$).

Each test case should contain one integer $n$ ($1 \leq n \leq 10^9$) on a separate line.

Note

For example, the number of unit bits in number $6$ is $2$, because binary notation of $6$ is $110$. For $13$ the number of unit bits is $3$, because $13_{10} = 1101_2$.

In the first test case, $n = 1$, so the input is the number $1$. After subtracting one from $n$, it becomes zero, so the number of unit bits in it is $0$.

In the third test case, $n = 3$, which in binary representation looks like $3_{10} = 11_2$, so the input is the number of ones, that is $2$. After subtracting $2$, $n = 1$, so the number of unit bits is now $1$. After subtracting one from $n$, it becomes equal to zero.

Note that the blank lines in the input and output examples are shown for clarity and are not present in the actual interaction.