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

令 $f(x)$ 为 $x$ 的二进制对数（即以 $2$ 为底的对数）的下取整。换言之，$f(x)$ 是满足 $2^y \leq x$ 的最大非负整数 $y$。

令 $g(x)$ 为 $x$ 以 $f(x)$ 为底的对数的下取整。换言之，$g(x)$ 是满足 ${f(x)}^{z} \leq x$ 的最大非负整数 $z$。

你将收到 $q$ 个查询。第 $i$ 个查询包含两个整数 $l_i$ 和 $r_i$。该查询的答案为所有满足 $l_i \leq k \leq r_i$ 的整数 $k$ 对应的 $g(k)$ 值之和。由于答案可能很大，请将结果对 ${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}$).

第一行包含一个整数 $q$ —— 查询的个数（$1 \leq q \leq 10^5$）。

接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$ —— 第 $i$ 个查询的边界（$4 \leq l_i \leq r_i \leq 10^{18}$）。

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

对于每个查询，输出该查询的答案对 $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$

下表列出了所有满足 $1 \leq x \leq 8$ 的 $x$ 对应的函数 $f(x)$ 和 $g(x)$ 的值。

$x$

$1$

$2$

$3$

$4$

$5$

$6$

$7$

$8$

$f$

$0$

$1$

$1$

$2$

$2$

$2$

$2$

$3$

$g$

$-$

$-$

$-$

$2$

$2$

$2$

$2$

$1$