FACTDIV - Factorial and divisorss

no tags 

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

hide comments
ashishranjan28: 2017-01-16 16:28:51

any hint..?

Nishant Gupta: 2016-05-27 08:31:55

Nice one :)

[Lakshman]: 2016-03-22 16:26:19

what is the expected complexity?


Added by:ashish kumar
Date:2016-03-17
Time limit:1s-2.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:self