存在一个无限长度的序列 $$$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]$$$。