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.