Description:
This is an interactive problem.
This is the game version of the problem. Note that the solution of this problem may or may not share ideas with the solution of the solo version. You can solve and get points for both versions independently.
Alice and Bob are playing a game. The game starts with a positive integer $$$n$$$, with players taking turns. On each turn of the game, the following sequence of events takes place:
- The player having the integer $$$p$$$ breaks it into two integers $$$p_{1}$$$ and $$$p_{2}$$$, where $$$0 \lt p_{1} \lt p$$$, $$$0 \lt p_{2} \lt p$$$ and $$$p_{1} \oplus p_{2} = p$$$.
- If no such $$$p_{1}$$$, $$$p_{2}$$$ exist, the player loses.
- Otherwise, the opponent does either select the integer $$$p_{1}$$$ or $$$p_{2}$$$.
- The game continues with the selected integer. The opponent will try to break it.
As Alice, your goal is to win. You can execute a maximum of $$$63$$$ break operations. You have the choice to play first or second. The system will act for Bob.
Here $$$\oplus$$$ denotes the bitwise XOR operation.
Input Format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.
The only line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$) — the number the game starts with.
Output Format:
None
Note:
Explanation for the interaction.
Interactor / BobAliceExplanation4$$$t$$$1$$$n$$$ for the first test casesecondAlice chooses to go second0 0Bob says he cannot break $$$p = 1$$$3$$$n$$$ for the second test casefirstAlice chooses to go first1 2Alice breaks $$$p = 3$$$ into $$$p_1 = 1$$$ and $$$p_2 = 2$$$0 0Bob says he cannot break $$$p = 1$$$ or $$$p = 2$$$13$$$n$$$ for the third test casefirstAlice chooses to go first10 7Alice breaks $$$p = 13$$$ into $$$p_1 = 10$$$ and $$$p_2 = 7$$$3 4Bob breaks $$$p = 7$$$ into $$$p_1 = 3$$$ and $$$p_2 = 4$$$1 2Alice breaks $$$p = 3$$$ into $$$p_1 = 1$$$ and $$$p_2 = 2$$$0 0Bob says he cannot break $$$p = 1$$$ or $$$p = 2$$$777777770001$$$n$$$ for the fourth test casefirstAlice chooses to go first777777770000 1Alice breaks $$$p = 777\,777\,770\,001$$$ into $$$p_1 = 777\,777\,770\,000$$$ and $$$p_2 = 1$$$0 0Bob says he cannot perform break operation.
This table is for explanation only and does not reflect the actual behavior of the interactor.
Note that in the last test case Bob could choose $$$p_1$$$ and perform a break operation but he gave up.