You have given number of testcases.

Each testcase 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 testcase. 

Next T line contains space separated two integer L and R.

1 <= T <= 1000000

1 <= L <= R <=1000000

Output

For each testcase 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