You are given a sequence whose first and the second elements are 0 and 1 respectively.
The $i^{th}$ element of sequence is given by:

$b_i$ = $(-1)^{i+1}$ * $[ |b_{i-1}| + |b_{i-2}| ]$

where |K| represents the absolute value of K. If the element is very large, take modulo with $10^9+7$.
Write a program to find the sum of the sequence having indexes between L and R (L and R inclusive). If the answer is very large, output it as modulo $10^9+7$. It is guaranteed that result will always be positive.

Input Format
First line: T, the number of test cases
Next T lines: L and R

Output Format
For each test case, output an integer which is the sum of all elements having indexes between L and R of the given sequence.

Input Constraints:
$1 \le T \le 10^4$
$0 \le L \le 10^{15}$
$L \le R \le 10^{15}$
0-based indexing is followed.