ANTP - Mr. Ant & His Problem

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

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


Added by:Alim
Date:2016-04-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own Problem

hide comments
2018-04-29 04:39:46
I want to know FFT is ok?
2016-08-14 15:37:20 Sidharth Sikri
can someone tell me, why am i getting a WA for my code -- http://ideone.com/4POTiA
my code passes the sample test case and also the test cases given here by @nhari
2016-05-21 18:18:47
5
2 10
5 26
23 59
100 500
30 89
answers are:
120
2596
30969
20551651
109910
2016-04-11 00:18:02
intersting but irritating ..(^_^)
2016-04-03 16:50:44 Jitesh
@aqua_regia. answer will be 0.
2016-04-03 10:57:58
Are there any special test cases. What if x=1 y=2 ? Is the answer 0 or 1. And provide some additional test cases.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.