D. Подозрительные логарифмы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пусть $$$f$$$($$$x$$$) — это округленный вниз двоичный логарифм $$$x$$$. То есть $$$f$$$($$$x$$$) — наибольшее такое целое неотрицательное число $$$y$$$, что $$$2^y$$$ не превосходит $$$x$$$.

Пусть $$$g$$$($$$x$$$) — это округленный вниз логарифм числа $$$x$$$ по основанию $$$f$$$($$$x$$$). То есть $$$g$$$($$$x$$$) — наибольшее такое целое неотрицательное число $$$z$$$, что $$${f(x)}^{z}$$$ не превосходит $$$x$$$.

Вам даны $$$q$$$ запросов. $$$i$$$-й запрос выглядит как два числа $$$l_i$$$, $$$r_i$$$. Ответом на запрос является сумма $$$g$$$($$$k$$$) по всем целым положительным $$$k$$$ таким, что $$$l_i \leq k \leq r_i$$$. Ответы на запросы выводите по модулю $$${10^9 + 7}$$$.

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

В первой строке дано число $$$q$$$ — число запросов ($$$1 \leq q \leq 10^5$$$).

В следующих $$$q$$$ строках заданы два числа $$$l_i$$$, $$$r_i$$$ — границы отрезка $$$i$$$-го запроса ($$$4 \leq l_i \leq r_i \leq 10^{18}$$$).

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

Для каждого запроса выведите ответ на него по модулю $$$10^9 + 7$$$.

Пример
Входные данные
12
4 6
4 7
4 8
4 100000
179 1000000000000000000
57 179
4 201018959
7 201018960
729 50624
728 50624
728 50625
729 50625
Выходные данные
6
8
9
348641
41949982
246
1
0
149688
149690
149694
149692
Примечание

В таблице снизу приведены значения функций $$$f$$$($$$x$$$) и $$$g$$$($$$x$$$) при целых $$$x$$$, таких что $$$1 \leq x \leq 8$$$.

$$$x$$$$$$1$$$$$$2$$$$$$3$$$$$$4$$$$$$5$$$$$$6$$$$$$7$$$$$$8$$$
$$$f$$$$$$0$$$$$$1$$$$$$1$$$$$$2$$$$$$2$$$$$$2$$$$$$2$$$$$$3$$$
$$$g$$$$$$-$$$$$$-$$$$$$-$$$$$$2$$$$$$2$$$$$$2$$$$$$2$$$$$$1$$$