B. Черепаха и бесконечная последовательность
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть последовательность $$$a_0, a_1, a_2, \ldots$$$ бесконечной длины. Изначально $$$a_i = i$$$ для каждого неотрицательного целого $$$i$$$.

Каждый элемент последовательности будет одновременно изменяться через каждую секунду. $$$a_i$$$ изменится на $$$a_{i - 1} \mid a_i \mid a_{i + 1}$$$ для каждого положительного целого $$$i$$$. $$$a_0$$$ изменится на $$$a_0 \mid a_1$$$. Здесь $$$|$$$ обозначает побитовое ИЛИ.

Черепаха должна найти значение $$$a_n$$$ после $$$m$$$ секунд. В частности, если $$$m = 0$$$, то он должен найти начальное значение $$$a_n$$$. Он устал вычислять так много значений, поэтому пожалуйста, помогите ему!

Входные данные

Каждый тест содержит несколько тестовых случаев. Первая строка содержит количество тестов $$$t$$$ ($$$1 \le t \le 10^4$$$). Затем следует описание тестов.

Первая строка каждого теста содержит два целых числа $$$n, m$$$ ($$$0 \le n, m \le 10^9$$$).

Выходные данные

Для каждого теста выведите одно целое число — значение $$$a_n$$$ после $$$m$$$ секунд.

Пример
Входные данные
9
0 0
0 1
0 2
1 0
5 2
10 1
20 3
1145 14
19198 10
Выходные данные
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]$$$.