CF2190F.Xor Product

For non-negative integers $x, y$ and a positive integer $k$, let $S(x, y, k)$ be the set of values $(x + i) \oplus (y + j)$ for all $0 \le i, j \lt k$. Formally: $$ S(x, y, k) = \{ (x + i) \oplus (y + j) \mid 0 \le i, j \lt k \} $$ where $\oplus$ denotes the bitwise XOR operation.

Define $f(x, k)$ as the maximum size of $S(x, y, k)$ over all non-negative integers $y$ (that is, $y \ge 0$).

You are given integers $x$ and $k$. Compute $f(x, k)$.

对于非负整数 $x, y$ 和正整数 $k$，定义集合 $S(x, y, k)$ 为所有满足 $0 \le i, j < k$ 的 $(x + i) \oplus (y + j)$ 的取值构成的集合。形式化地：

$$S(x, y, k) = \{ (x + i) \oplus (y + j) \mid 0 \le i, j < k \}$$

其中 $\oplus$ 表示按位异或（XOR）运算。

定义 $f(x, k)$ 为：在所有非负整数 $y$（即 $y \ge 0$）中，$S(x, y, k)$ 的最大大小。

给定整数 $x$ 和 $k$，请计算 $f(x, k)$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

Each of the next $t$ lines contains two integers $x$ and $k$ ($1 \le x, k \le 10^{17}$).

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是测试用例的描述。

接下来的 $t$ 行中，每行包含两个整数 $x$ 和 $k$（$1 \le x, k \le 10^{17}$）。

For each test case, output a single integer — the value of $f(x, k)$.

对于每个测试用例，输出一个整数——即 $f(x, k)$ 的值。

In the first example, since $k=1$, the set $S$ will always contain exactly one element regardless of $y$. For instance, if we pick $y = 69$, we have $S(67, 69, 1) = {67 \oplus 69} = {6}$, so $|S(x, y, k)| = 1$.

In the second example, we have $x = 7$ and $k = 3$. The optimal choice is $y = 8$. The values of $(x + i) \oplus (y + j)$ are: $$ [7 \oplus 8, 7 \oplus 9, 7 \oplus 10, 8 \oplus 8, 8 \oplus 9, 8 \oplus 10, 9 \oplus 8, 9 \oplus 9, 9 \oplus 10] $$ which simplifies to $[15, 14, 13, 0, 1, 2, 1, 0, 3]$. The set of distinct values is $S(7, 8, 3) = {0, 1, 2, 3, 13, 14, 15}$, so the size is $7$. It can be shown that no other $y$ yields a larger size. However, the choice of $y$ matters; for example, if you chose $y = 22$, you would get $S(7, 22, 3) = {16, 17, 30, 31}$ with size $4$, which is suboptimal.

In the sixth example, after countless calculations, we managed to figure out that the optimal $y$ is $278\,302\,368\,699\,121\,665$, which gives an answer of $398\,158\,383\,604\,301\,822$. The proof is left to the reader as a trivial exercise.

在第一个例子中，由于 $k=1$，集合 $S$ 无论 $y$ 取何值都恰好包含一个元素。例如，若取 $y = 69$，则有 $S(67, 69, 1) = \{67 \oplus 69\} = \{6\}$，因此 $|S(x, y, k)| = 1$。

在第二个例子中，$x = 7$ 且 $k = 3$。最优选择为 $y = 8$。此时 $(x + i) \oplus (y + j)$ 的所有取值为：

$$[7 \oplus 8,\ 7 \oplus 9,\ 7 \oplus 10,\ 8 \oplus 8,\ 8 \oplus 9,\ 8 \oplus 10,\ 9 \oplus 8,\ 9 \oplus 9,\ 9 \oplus 10]$$

化简后得到 $[15,\ 14,\ 13,\ 0,\ 1,\ 2,\ 1,\ 0,\ 3]$。其互异值构成的集合为 $S(7, 8, 3) = \{0,\ 1,\ 2,\ 3,\ 13,\ 14,\ 15\}$，故集合大小为 $7$。可以证明，不存在其他 $y$ 值能使该大小更大。然而，$y$ 的选取至关重要；例如，若选取 $y = 22$，则得到 $S(7, 22, 3) = \{16,\ 17,\ 30,\ 31\}$，其大小仅为 $4$，非最优。

在第六个例子中，经过无数次计算，我们最终确定最优的 $y$ 值为 $278\,302\,368\,699\,121\,665$，对应答案为 $398\,158\,383\,604\,301\,822$。该结论的证明留作读者的一项平凡练习。