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

Explanation for the first test case

Way 01

Way 02

Way 03

Way 04

Way 05

Way 06

Way 07

Way 08

Way 09

Note: use faster i/o method.

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