Bit Guessing Game
Contest: Codeforces Round 846 (Div. 2)
Difficulty rating: 1800
Tags: binary search, bitmasks, constructive algorithms, interactive

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 format:
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 format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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.

Example input:
3

1

0

1

1

0

2

1

0

Example output:
- 1

! 1

- 1

- 1

! 2

- 2

- 1

! 3

Editorial:
There are two similar solutions to this problem, we will tell you both.
The first, simpler one: subtract $$$1$$$. What can we say now about the number of units at the beginning of the binary notation of a number? There are exactly $$$cnt - cnt_w - 1$$$, where $$$cnt$$$ is the number of unit bits after subtracting the unit, and $$$cnt_w$$$ is— before subtracting. Now we subtract them, for this we need to subtract the number $$$2^{cnt - cnt_w - 1} - 1$$$ and continue the algorithm. But such an algorithm makes at worst $$$60$$$ requests. To save queries, note that we know the number of units after we remove the units from the beginning, therefore it is useless to make another request for this. Then at the same time, as we remove the units from the beginning, we will immediately subtract the unit. As a result, there will be absolutely no more than $$$cnt$$$ operations, where $$$cnt$$$ is the initial number of single bits in the record of the number $$$n$$$. This number does not exceed $$$O(log_2(n))$$$, in turn, $$$log_2(n)$$$ does not exceed 30, which fits into the restrictions.
The second solution. Let $$$ans$$$ be the desired number $$$n$$$, and $$$was$$$ be the initial number of bits in the number $$$n$$$. Let's subtract the powers of two : $$$2^0, 2^1, 2^2, ... 2^ k$$$, while $$$was$$$ it will not become 0. We will support the $$$Shift$$$ flag - whether there was a bit transfer to $$$n$$$ when subtracting any power of two. Suppose we subtracted $$$2^k$$$ at the $$$k$$$th step and the number of bits became equal to $$$cnt_{new}$$$, and before the subtraction was $$$cnt$$$, then consider two cases.
1) $$$cnt - cnt_{new} = 1$$$, then bit $$$k$$$ was included in $$$n$$$ at the $$$k$$$th step, and if $$$Shift = false$$$, then we add to $$$ans$$$ — $$$2^k$$$, since there was no bit transfer, which means bit k is also in the original number, and subtract from $$$was$$$ — $$$1$$$. If $$$Shift = true$$$, then we added this bit during previous operations, and it does not need to be taken into account.
2) $$$cnt - cnt_{new} \neq 1$$$, then we know that the number of bits has not decreased, also that in the number $$$n$$$ there was such a bit $$$m$$$ that $$$2^m > 2^k$$$, and at the same time the bit $$$m$$$ is in $$$n$$$. Moreover, $$$m - k - 1 = cnt_{new} - cnt$$$. So $$$m = k + 1 + cnt_{new} - cnt$$$. Let's add $$$2^m$$$ to the answer, subtract from $$$was$$$ — $$$1$$$ and assign the $$$Shift$$$ flag the value $$$true$$$, since there was a bit transfer.
Thus, we found the initial number $$$n$$$, which is equal to $$$ans$$$, and also made no more than $$$O(log_2(n))$$$ queries, since $$$k\le log_2(n)$$$.
Thus, the solution spends no more than 30 requests, which fits into the limitations of the task.