CF1780D Bit Guessing Game

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.

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 $ .

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.

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.