Nobita’s teacher gave him a Sequence ( $a_{i}$ ) of natural numbers as homework which is defined as follows:

$a_{1}$ = 1
$a_{2}$ = 10
$a_{i}$ = $a_{i-1}$ + $2a_{i-2}$

Now his teacher ask to compute $a_{m}$ + $a_{m+1}$ + $a_{m+2}$ + ... + $a_{n}$ for given m ≤ n and output it modulo $10^{9}$ +7. As Nobita is very weak in Mathematics so he asks Doraemon for his help. But Doraemon has to go to date with Mii Chan so he is asking for your help. Can you help Doraemon with this given task.

Input:
First line contain T i.e., no. of test cases. Each test-case contains two space separated integers m and n as described in the problem.

Output:
Exactly T lines, one for each test case: ($a_{m}$ + $a_{m+1}$ + $a_{m+2}$ + ... + $a_{n}$) modulo $10^{9}$ +7.

Constraints:

Subtask 1: 20 points
1 ≤ T ≤ 10
1 ≤ m ≤ n < $10^{5}$

Subtask 2: 60 points
1 ≤ T ≤ 1000
1 ≤ m ≤ n < $10^{16}$