Mr. Ant has 3 boxes and the infinite number of marbles. Now he wants to know the number of ways he can put marbles in these three boxes when the following conditions hold.

• Each box must contain at least 1 marble.
• The summation of marbles of the 3 boxes must be in between X and Y inclusive.

Now you are given X and Y. You have to find the number of ways Mr. Ant can put marbles in the 3 boxes.

Input

Input starts with an integer T, denoting the number of test cases. Each test case contains two integers X and Y.

Constraints

1 ≤ T ≤ 1000000

1 ≤ X ≤ Y ≤ 1000000

Output

For each test case, print the required answer modulo 1000000007.

Example

Input:
1
4 5
Output:
9

</p>

Explanation for the first test case

1

1

2

Way 01

1

1

3

Way 02

1

2

1

Way 03

1

3

1

Way 04

2

1

1

Way 05

3

1

1

Way 06

1

2

2

Way 07

2

1

2

Way 08

2

2

1

Way 09

Note: use faster i/o method.

Problem Setter: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business & Technology