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 109+7

Input

First line consists 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

Added by:avinash
Date:2012-04-08
Time limit:2.772s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own

hide comments
2023-03-24 06:12:29 Ishan
@Mitch Now that I have solved it, can I know your solution? You can add my gmail for a private chat, it's same as my handle.
2014-04-19 17:31:43 Kanish_The_Vista
@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...
2014-04-11 13:55:18 Zeus
@admin can you please tell me why am i getting runtime error ???? i think my algo is correct... please help... id: 11425187

sorry got it... ac :)

Last edit: 2014-04-11 14:15:34
2013-08-22 04:54:11 Somesh Maurya™
in 0.04 sec???how man??
2013-06-29 21:39:58 Mitch Schwartz
@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.
2013-06-29 21:30:36 Yashpal
Can someone give me some link so that i can learn more about sum of the LCM....
I searched a lot in google but can't get it....
EDIT-->finally got AC...:)

Last edit: 2013-08-16 14:45:30
2013-06-17 19:19:41 Hariharan
used euclid's algorithm to find the lcm, but i'm still getting TLE. I wonder how Mitch solved it under 0.04s!!!!

thanks @Mitch.

Last edit: 2013-07-06 09:58:16
2012-12-25 13:00:54 Ashish Lavania
nice! first try AC!!
2012-04-10 23:10:30 Runtime Error
tle :(
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.