对于非负整数 $$$x, y$$$ 和正整数 $$$k$$$,令 $$$S(x, y, k)$$$ 为所有 $$$0 \le i, j \lt k$$$ 的值集 $$$(x + i) \oplus (y + j)$$$。形式上: $$S(x, y, k) = \{ (x + i) \oplus (y + j) \mid 0 \le i, j \lt k \}$$ 其中 $$$\oplus$$$ 表示按位异或运算。
将 $$$f(x, k)$$$ 定义为 $$$S(x, y, k)$$$ 在所有非负整数 $$$y$$$ 上的最大大小(即 $$$y \ge 0$$$)。
给定整数 $$$x$$$ 和 $$$k$$$。计算 $$$f(x, k)$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
接下来的 $$$t$$$ 行包含两个整数 $$$x$$$ 和 $$$k$$$ ($$$1 \le x, k \le 10^{17}$$$)。
输出
对于每个测试用例,输出一个整数 - $$$f(x, k)$$$ 的值。
示例
输入复制
667 17 3100 121 10431526 104388946092640567295 100000000000000000
输出复制
173231284167398158383604301822
注意
在第一个示例中,由于 $$$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$$$。证明留给读者作为一个简单的练习。