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

В ходе проведения очередной весенней уборки, Даниэль нашел старый калькулятор, который ему очень понравился. Однако кажется, что что-то в нем сломано. Когда он хочет посчитать $$$1 + 3$$$ c помощью калькулятора, он получает $$$2$$$ вместо $$$4$$$. Но при вычислении $$$1 + 4$$$ ответ получается правильный, $$$5$$$. Озадаченный таким поведением, он вскрыл калькулятор и нашел разгадку: полные сумматоры стали полусумматорами!

Теперь, когда он хочет посчитать $$$a + b$$$ при помощи калькулатора, он получает ксор-сумму $$$a \oplus b$$$ (определение можно прочитать по ссылке: https://ru.wikipedia.org/wiki/Сложение_по_модулю_2).

Но как он уже заметил ранее, калькулятор иногда выдает правильные ответы. Поэтому его интересует, при данных $$$l$$$ и $$$r$$$ сколько существует таких пар целых чисел $$$(a, b)$$$, для которых выполняются следующие условия: $$$$$$a + b = a \oplus b$$$$$$ $$$$$$l \leq a \leq r$$$$$$ $$$$$$l \leq b \leq r$$$$$$

Даниэль Бармен, однако, сейчас направляется в бар, а вернется только через пару часов. Он советует вам решить эту задачу до его возвращения, или же вы будете забанены.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных в тесте.

Затем следует $$$t$$$ строк, в каждой записаны по два целых числа $$$l$$$ и $$$r$$$ ($$$0 \le l \le r \le 10^9$$$).

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

Выведите $$$t$$$ целых чисел, $$$i$$$-е число должно быть ответом на $$$i$$$-й набор входных данных.

Пример
Входные данные
3
1 4
323 323
1 1000000
Выходные данные
8
0
3439863766
Примечание

$$$a \oplus b$$$ обозначает побитовое исключающее ИЛИ $$$a$$$ и $$$b$$$.

В первом примере подходящие пары: $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(2, 1)$$$, $$$(2, 4)$$$, $$$(3, 4)$$$, $$$(4, 1)$$$, $$$(4, 2)$$$, и $$$(4, 3)$$$.