Dharam was sitting in his hostel. He found a magical wand in Shikhar's room. The wand generates a magical series:

• 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, ..........

Dharam realised that wand works on a magical function F(N) for some magical integer N, such that F(N) represents the N^th term of the magical series.

For two more magical integers L and R, Dharam wants to find the integer S:

• S = F(L) + F(L + 1) + ... + F(R - 1) + F(R)

Dharam wants to find S % M, for M = 1000000007 (10⁹ + 7).

Input

First line of input is an integer T, total number of test cases, followed by T lines. Each line consists of two space separated integers L and R.

Output

Output S % M in single line for each test case.

Constraints

• 1 <= T <= 1000000 (10⁶)
• 1 <= L, R <= 50000000000 (5 x 10¹⁰)
• L <= R

Note: Large input data. Use fast I/O.