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.

Idx	Name	Rating
A	Hayato and School	800
B	GCD Partition	1100
D	Bit Guessing Game	1800
E	Josuke and Complete Graph	2400
F	Three Chairs	2300
G	Delicious Dessert	2400

Codeforces Round 846 (Div. 2)