CF1934D2.XOR Break — Game Version

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.

这是一个交互式问题。

这是该问题的游戏版本。请注意，本题的解法可能与单人版本的解法思路相同，也可能不同。你可以独立求解并分别获得两个版本的分数。

爱丽丝（Alice）和鲍勃（Bob）正在玩一个游戏。游戏开始时给定一个正整数 $n$，双方轮流进行操作。在每一轮游戏中，将依次发生以下事件：

• 当前持有整数 $p$ 的玩家将其拆分为两个整数 $p_{1}$ 和 $p_{2}$，满足 $0 \lt p_{1} \lt p$、$0 \lt p_{2} \lt p$，且 $p_{1} \oplus p_{2} = p$。
• 若不存在满足上述条件的 $p_{1}$、$p_{2}$，则该玩家输掉游戏。
• 否则，对手从 $p_{1}$ 和 $p_{2}$ 中任选其一。
• 游戏以所选整数继续进行，对手将尝试对该整数进行拆分。

作为爱丽丝，你的目标是获胜。你最多可执行 $63$ 次拆分操作。你可以选择先手或后手。系统将代表鲍勃进行操作。

此处 $\oplus$ 表示按位异或运算。

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.

每个测试包含多个测试用例。输入的第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。

每个测试用例仅一行，包含一个整数 $n$（$1 \leq n \leq 10^{18}$），表示游戏开始时的数字。

Explanation for the interaction.

Interactor / Bob

Alice

Explanation

4

$t$

1

$n$ for the first test case

second

Alice chooses to go second

0 0

Bob says he cannot break $p = 1$

3

$n$ for the second test case

first

Alice chooses to go first

1 2

Alice breaks $p = 3$ into $p_1 = 1$ and $p_2 = 2$

0 0

Bob says he cannot break $p = 1$ or $p = 2$

13

$n$ for the third test case

first

Alice chooses to go first

10 7

Alice breaks $p = 13$ into $p_1 = 10$ and $p_2 = 7$

3 4

Bob breaks $p = 7$ into $p_1 = 3$ and $p_2 = 4$

1 2

Alice breaks $p = 3$ into $p_1 = 1$ and $p_2 = 2$

0 0

Bob says he cannot break $p = 1$ or $p = 2$

777777770001

$n$ for the fourth test case

first

Alice chooses to go first

777777770000 1

Alice breaks $p = 777\,777\,770\,001$ into $p_1 = 777\,777\,770\,000$ and $p_2 = 1$

0 0

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

交互过程说明。

交互器 / Bob

Alice

说明

4

$t$

1

第一个测试用例的 $n$

second

Alice 选择后手

0 0

Bob 表示无法对 $p = 1$ 进行拆分

3

第二个测试用例的 $n$

first

Alice 选择先手

1 2

Alice 将 $p = 3$ 拆分为 $p_1 = 1$ 和 $p_2 = 2$

0 0

Bob 表示无法对 $p = 1$ 或 $p = 2$ 进行拆分

13

第三个测试用例的 $n$

first

Alice 选择先手

10 7

Alice 将 $p = 13$ 拆分为 $p_1 = 10$ 和 $p_2 = 7$

3 4

Bob 将 $p = 7$ 拆分为 $p_1 = 3$ 和 $p_2 = 4$

1 2

Alice 将 $p = 3$ 拆分为 $p_1 = 1$ 和 $p_2 = 2$

0 0

Bob 表示无法对 $p = 1$ 或 $p = 2$ 进行拆分

777777770001

第四个测试用例的 $n$

first

Alice 选择先手

777777770000 1

Alice 将 $p = 777\,777\,770\,001$ 拆分为 $p_1 = 777\,777\,770\,000$ 和 $p_2 = 1$

0 0

Bob 表示无法执行拆分操作。

本表格仅用于说明，不反映交互器的实际行为。

注意：在最后一个测试用例中，Bob 本可选择 $p_1$ 并执行拆分操作，但他放弃了。