A16345. Suspicious logarithms

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

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

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

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$