ADDLCMS - 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
CHALLENGE : Minimum Source code

Added by:avinash
Date:2016-03-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:GAWK MAWK BASH BC BF C NCSHARP C++ 4.3.2 CPP CPP14 C99 COFFEE DART FORTH JAVA JULIA KTLN OCT PERL PERL6 PROLOG PYTHON PYPY3 PYTHON3 PY_NBC R RACKET RUBY SCALA SQLITE SWIFT UNLAMBDA
Resource:http://www.spoj.com/problems/ADDLCM/

hide comments
2016-04-02 07:11:14 Mitch Schwartz
Now instead of internal error I get score 0. Please make sure test case judge is "Score is source length" (and not the default "Ignores extra whitespaces").

[Reply] Thanks Mitch. This is also changed.

Last edit: 2016-04-02 08:33:06
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.