You have given number of test cases.

Each test case have two space separated integer L and R. You have to find total value of fun(L) + fun(L+1) + ... + fun(R), where fun(x) is total number of positive divisors of x factorial. Since result may be large print it modulo 1000000007.

Input

First line of input contains T total number of test case. 

Next T lines contain two space-separated integers L and R.

1 <= T <= 1000000

1 <= L <= R <= 1000000

Output

For each test case output the result modulo 1000000007.

Example

Input:
10
1 9
6 7
2 4
7 8
1 3
10 10
3 5
6 7
1 10
6 6

Output:
377
90
14
156
7
270
28
90
647
30