310812: CF1891D. Suspicious logarithms

D. Suspicious logarithmstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

ExampleInput

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

6
8
9
348641
41949982
246
1
0
149688
149690
149694
149692

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$

题目大意：
给定一个函数 \( f(x) \)，表示 \( x \) 的二进制对数的向下取整，即最大的非负整数 \( y \)，使得 \( 2^y \leq x \)。再给定一个函数 \( g(x) \)，表示以 \( f(x) \) 为底的对数 \( x \) 的向下取整，即最大的非负整数 \( z \)，使得 \( f(x)^z \leq x \)。给定 \( q \) 个查询，每个查询由两个整数 \( l_i \) 和 \( r_i \) 组成。每个查询的答案是对于所有满足 \( l_i \leq k \leq r_i \) 的整数 \( k \)，\( g(k) \) 的和。由于答案可能很大，所以输出答案模 \( 10^9 + 7 \) 的结果。

输入输出数据格式：
输入：
- 第一行包含一个整数 \( q \)（\( 1 \leq q \leq 10^5 \)），表示查询的数量。
- 接下来的 \( q \) 行，每行包含两个整数 \( l_i \) 和 \( r_i \)（\( 4 \leq l_i \leq r_i \leq 10^{18} \)），表示第 \( i \) 个查询的界限。

输出：
- 对于每个查询，输出该查询的答案模 \( 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) \)，表示 \( x \) 的二进制对数的向下取整，即最大的非负整数 \( y \)，使得 \( 2^y \leq x \)。再给定一个函数 \( g(x) \)，表示以 \( f(x) \) 为底的对数 \( x \) 的向下取整，即最大的非负整数 \( z \)，使得 \( f(x)^z \leq x \)。给定 \( q \) 个查询，每个查询由两个整数 \( l_i \) 和 \( r_i \) 组成。每个查询的答案是对于所有满足 \( l_i \leq k \leq r_i \) 的整数 \( k \)，\( g(k) \) 的和。由于答案可能很大，所以输出答案模 \( 10^9 + 7 \) 的结果。 输入输出数据格式： 输入： - 第一行包含一个整数 \( q \)（\( 1 \leq q \leq 10^5 \)），表示查询的数量。 - 接下来的 \( q \) 行，每行包含两个整数 \( l_i \) 和 \( r_i \)（\( 4 \leq l_i \leq r_i \leq 10^{18} \)），表示第 \( i \) 个查询的界限。 输出： - 对于每个查询，输出该查询的答案模 \( 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 ```