ADDLCM  lcm addition
Mao is very good in mathematics, he likes to play with numbers and number theory is his favorite chapter. Once he decided to give a question to kalyu his friend . Now Kalyu is always busy in writing articles, as he likes maths but articles is his passion and source of income too, so he can’t give much time solving that maths question, but he too don’t want to hurt his friend, so help kalu in his problem ?
Given a,b such that a<=b calculate the addition:
LCM(a,b) + LCM(a+1,b) + .. + LCM(b,b), where LCM(a,b) denotes the Least Common Multiple of the integers a and b.
Since, output may be very large, take the mod 10^9+7
Input
First line cosists of T=number of test cases, next T line will contain a and b
Output
For each T lines, print the required output.
Constraints
T<=100000
1 <= a <= b <= 1000000
Example
Input:
3
1 6
10 15
41 90
Output:
66
675
139860
hide comments
Kanish_The_Vista:
20140419 17:31:43
@AVINASH can u check my submission id:11465975,i m getting tle...i think so my algo is working fine but don't know why it does not pass the judge time... 

Zeus:
20140411 13:55:18
@admin can you please tell me why am i getting runtime error ???? i think my algo is correct... please help... id: 11425187


Somesh Maurya™:
20130822 04:54:11
in 0.04 sec???how man?? 

Somesh Maurya™:
20130822 04:35:17
Last edit: 20130822 04:54:24 

Mitch Schwartz:
20130629 21:39:58
@Yashpal, Hariharan: I didn't find any published work about this, it was a lot of work on paper, and I think it's a great problem. You may find it useful to work on LCMSUM first, it's related to this one and easier. 

Yashpal:
20130629 21:30:36
Can someone give me some link so that i can learn more about sum of the LCM....


Hariharan :
20130617 19:19:41
used euclid's algorithm to find the lcm, but i'm still getting TLE. I wonder how Mitch solved it under 0.04s!!!!


Ashish Lavania:
20121225 13:00:54
nice! first try AC!! 

Runtime Error:
20120410 23:10:30
tle :( 
Added by:  avinash 
Date:  20120408 
Time limit:  2.772s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own 