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