← 返回题目列表

Codeforces · 1981/B

B. 海龟和无限序列

中文机器翻译题面 查看原题

存在一个无限长度的序列 $$$a_0, a_1, a_2, \ldots$$$。最初,对于每个非负整数 $$$i$$$,$$$a_i = i$$$。

每秒之后,序列中的每个元素都会同时发生变化。对于每个正整数 $$$i$$$,$$$a_i$$$ 将更改为 $$$a_{i - 1} \mid a_i \mid a_{i + 1}$$$。 $$$a_0$$$ 将更改为 $$$a_0 \mid a_1$$$。这里,$$$|$$$ 表示按位或。

Turtle 被要求在 $$$m$$$ 秒后找到 $$$a_n$$$ 的值。特别是,如果$$$m = 0$$$,那么他需要找到$$$a_n$$$的初始值。他厌倦了计算这么多值,所以请帮助他!

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n, m$$$ ($$$0 \le n, m \le 10^9$$$)。

输出

对于每个测试用例,输出一个整数 - $$$a_n$$$ 在 $$$m$$$ 秒后的值。

示例

输入 #1

9
0 0
0 1
0 2
1 0
5 2
10 1
20 3
1145 14
19198 10

输出 #1

0
1
3
1
7
11
23
1279
19455

注意

$$$1$$$ 第二次之后,$$$[a_0, a_1, a_2, a_3, a_4, a_5]$$$ 将变为 $$$[1, 3, 3, 7, 7, 7]$$$。

$$$2$$$ 秒后,$$$[a_0, a_1, a_2, a_3, a_4, a_5]$$$ 将变为 $$$[3, 3, 7, 7, 7, 7]$$$。