[SOLUTION] Suspicious logarithms Solution Codeforces

Suspicious logarithms Solution Codeforces

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$ .

Example

input

Copy

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

output

Copy

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$

Leave a Comment Cancel reply