Codeforces Round 907 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

brute force

math

*1900

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Suspicious logarithms

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLet $$$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

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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/02/2023 04:29:33 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|