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

Let [MATH8] be the floor of the logarithm of $x$ with base [MATH11]. In other words, [MATH13] 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 [MATH22] 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$.

见题面 Input 部分

见题面 Output 部分

The table below contains the values of the functions [MATH13] and [MATH15] 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$