FACTDIV - Factorial and divisorss

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

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

hide comments
2018-09-13 23:44:05
Great problem. Prototyped in PyPy, precalc ran at 1.64s using BACTERIA; same program translated to C couldn't even precompute 50000 in the same time. Went cycling, had some sleep, figured out what needs to be done -- C solution speeded up 100+ times and subsequently ACd, yet PyPy now runs at 2.23s. Don't understand the world anymore...
2017-01-16 16:28:51
any hint..?
2016-05-27 08:31:55 Nishant Gupta
Nice one :)
2016-03-22 16:26:19 [Lakshman]
what is the expected complexity?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.