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

В джунглях есть озеро с бесконечным количеством кувшинок. Кувшинки пронумерованы неотрицательными целыми числами $$$0, 1, 2, 3, \ldots$$$. Кувшинки с номерами от $$$l$$$ до $$$r$$$ включительно называются подходящими, в то время как все остальные кувшинки не подходят для того, чтобы на них сидели лягушки.

В настоящее время на каждой подходящей кувшинке сидит по одной лягушке.

Остад наблюдает за озером и хочет переставить лягушек. Для этого Остад может выбрать положительное целое число $$$x$$$ и объявить его лягушкам. Услышав число, лягушка, сидящая на $$$i$$$-й кувшинке, прыгнет на $$$(i \oplus x)$$$-ю, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Остад любит лягушек, и поэтому он хочет выбрать число $$$x$$$ таким образом, чтобы все лягушки оставались в пределах подходящих кувшинок.

Помогите Остаду, подсчитав, сколько различных чисел $$$x$$$ он может выбрать так, чтобы ни одна лягушка не прыгнула за пределы подходящего сегмента кувшинок.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Для каждого набора есть одна строка, содержащая два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq 10^{15}$$$).

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

Для каждого набора выведите одно целое число, обозначающее количество допустимых значений для $$$x$$$.

Пример
Входные данные
5
1 2
3 3
2 4
4 7
24189255811072 59373627899903
Выходные данные
1
0
0
3
2199023255551
Примечание

В первом примере $$$x = 3$$$ — единственное число, которое Остад может выбрать, так как $$$1 \oplus 3 = 2$$$ и $$$2 \oplus 3 = 1$$$, которые находятся в пределах $$$[1, 2]$$$.

Второй и третий примеры не имеют допустимых вариантов для Остада. Во втором случае, поскольку мы требуем $$$x \gt 0$$$, единственная лягушка, которую мы имеем, покинет диапазон. Аналогично, в третьем случае не существует допустимого $$$x$$$, чтобы удержать лягушек в желаемом диапазоне.

В четвертом примере Остад может выбрать $$$1$$$, $$$2$$$ или $$$3$$$.

Ссылка на визуализатор