Let $$$f$$$($$$x$$$) be the floor of the binary logarithm of $$$x$$$. In other words, $$$f$$$($$$x$$$) is largest non-negative integer $$$y$$$, such that $$$2^y$$$ does not exceed $$$x$$$.

Let $$$g$$$($$$x$$$) be the floor of the logarithm of $$$x$$$ with base $$$f$$$($$$x$$$). In other words, $$$g$$$($$$x$$$) is the largest non-negative integer $$$z$$$, such that $$${f(x)}^{z}$$$ does not exceed $$$x$$$.

You are given $$$q$$$ queries. The $$$i$$$-th query consists of two integers $$$l_i$$$ and $$$r_i$$$. The answer to the query is the sum of $$$g$$$($$$k$$$) across all integers $$$k$$$, such that $$$l_i \leq k \leq r_i$$$. Since the answers might be large, print them modulo $$${10^9 + 7}$$$.

Input

The first line contains a single integer $$$q$$$ — the number of queries ($$$1 \leq q \leq 10^5$$$).

The next $$$q$$$ lines each contain two integers $$$l_i$$$ and $$$r_i$$$ — the bounds of the $$$i$$$-th query ($$$4 \leq l_i \leq r_i \leq 10^{18}$$$).

Output

For each query, output the answer to the query modulo $$$10^9 + 7$$$.

Note

The table below contains the values of the functions $$$f$$$($$$x$$$) and $$$g$$$($$$x$$$) for all $$$x$$$ such that $$$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$$$

Idx	Name	Rating
A	Sorting with Twos	800
B	Deja Vu	1100
C	Smilo and Monsters	1500
D	Suspicious logarithms	1900
E	Brukhovich and Exams	2500
F	A Growing Tree	2000

Codeforces Round 907 (Div. 2)