# [SOLUTION] Suspicious logarithms Solution Codeforces

Suspicious logarithms Solution Codeforces
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard 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 2y2� 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 li�� and ri��. The answer to the query is the sum of g(k) across all integers k, such that likri��≤�≤��. Since the answers might be large, print them modulo 109+7109+7.

Input

The first line contains a single integer q — the number of queries (1q1051≤�≤105).

The next q lines each contain two integers li�� and ri�� — the bounds of the i-th query (4liri10184≤��≤��≤1018).

Output

For each query, output the answer to the query modulo 109+7109+7.

Example
input

Copy
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

Copy
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 1x81≤�≤8.

 x� 11 22 33 44 55 66 77 88 f� 00 11 11 22 22 22 22 33 g� −− −− −− 22 22 22 22 11