The sequence of Tetranacci numbers is defined as follows:
a_n = a_n-1 + a_n-2 + a_n-3 + a_n-4 with a₀ = a₁ = a₂ = 0 and a₃ = 1.

Input

Input starts with a positive integer t ≤ 4000, then t lines follow. Each of the t lines contains two space separated integers m and n with 0 ≤ m ≤ n ≤ 10⁹.

Output

Calculate a_m + a_m+1 + ... + a_n and print the result modulo 1000000007.

Example

Input:
2
1 2
1919 5393
Output:
0
66616

Note: If your solution times out, you may try the tutorial version first.