F. XOR произведение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для целых неотрицательных чисел $$$x, y$$$ и целого положительного числа $$$k$$$, пусть $$$S(x, y, k)$$$ — это множество значений $$$(x + i) \oplus (y + j)$$$ для всех $$$0 \le i, j \lt k$$$. Формально: $$$$$$ S(x, y, k) = \{ (x + i) \oplus (y + j) \mid 0 \le i, j \lt k \} $$$$$$ где $$$\oplus$$$ обозначает побитовую операцию XOR.

Определим $$$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)$$$.

Пример
Входные данные
6
67 1
7 3
100 12
1 1043
1526 1043
88946092640567295 100000000000000000
Выходные данные
1
7
32
3128
4167
398158383604301822
Примечание

В первом наборе входных данных, поскольку $$$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$$$. Доказательство оставлено читателю в качестве тривиального упражнения.