D. Bit Guessing Game
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.
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\).
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.