Kaushik loves to find the amount of goodness in everything. He wants to use a range of numbers in one of his projects. He has certain ranges in mind. He needs you to help him find the goodness of all integers in that range. The goodness of a number is the number multiplied by its length. For example, the goodness of 45 is 45×2 = 90.

Kaushik already has lame algorithms. So he wants you to find some faster algorithms. Help him find the range that is good.

Since the output can be really large, print output modulo 10^9+7.

Given two integers a and b, find the sum of the goodness of all numbers from a <= i <= b.

Input

First line consists of t, number of test cases.

For each test case, there are two integers a and b, denoting the beginning and the ending numbers

1 <= t <= 100

1 <= a <= b <= 1000000000

Output

Output a line for each test case containing the required answer modulo 10^9+7.

Example

Input:
1
9 12

Output:
75

Explanation

9×1 + 10×2 + 11×2 + 12×2 = 75