MOD = 1000000007;
function copy(a, b) {
a[0][0] = b[0][0];
a[0][1] = b[0][1];
a[1][0] = b[1][0];
a[1][1] = b[1][1];
}
function multiply(fib, base) {
let mat = [[], []];
copy(mat, fib);
mat[0][0] = (fib[0][0]*base[0][0] + fib[0][1]*base[1][0]) % MOD;
mat[0][1] = (fib[1][0]*base[0][0] + fib[1][1]*base[1][0]) % MOD;
mat[1][0] = (fib[0][0]*base[0][1] + fib[0][1]*base[1][1]) % MOD;
mat[1][1] = (fib[1][0]*base[0][1] + fib[1][1]*base[1][1]) % MOD;
copy(fib, mat);
}
function calcMatrix(fib, n) {
const base = [[1,1], [1,0]];
fib[0][0] = 1;
fib[0][1] = 0;
fib[1][0] = 0;
fib[1][1] = 1;
while (n) {
if (n&1) {
multiply(fib, base);
}
multiply(base, base);
n = n.toString(2).slice(0, -1);
}
}
let t = parseInt(readline());
while(t--)
{
[N, M] = readline().split(' ');
N = Number(N);
M = Number(M);
let fib = [[],[]];
calcMatrix(fib, N);
let fn = fib[0][1];
let fn1 = fib[1][1] ;
calcMatrix(fib, M-N+2);
let sum = ((fib[0][0]-1)*fn % MOD + (fib[0][1]-1)*fn1 % MOD + MOD) % MOD;
print(sum);
}
TU9EID0gMTAwMDAwMDAwNzsKCmZ1bmN0aW9uIGNvcHkoYSwgYikgewoJYVswXVswXSA9IGJbMF1bMF07CglhWzBdWzFdID0gYlswXVsxXTsKCWFbMV1bMF0gPSBiWzFdWzBdOwoJYVsxXVsxXSA9IGJbMV1bMV07Cn0KCmZ1bmN0aW9uIG11bHRpcGx5KGZpYiwgYmFzZSkgewoJbGV0IG1hdCA9IFtbXSwgW11dOwoJY29weShtYXQsIGZpYik7CgkKCW1hdFswXVswXSA9IChmaWJbMF1bMF0qYmFzZVswXVswXSArIGZpYlswXVsxXSpiYXNlWzFdWzBdKSAlIE1PRDsKICAgIG1hdFswXVsxXSA9IChmaWJbMV1bMF0qYmFzZVswXVswXSArIGZpYlsxXVsxXSpiYXNlWzFdWzBdKSAlIE1PRDsKICAgIG1hdFsxXVswXSA9IChmaWJbMF1bMF0qYmFzZVswXVsxXSArIGZpYlswXVsxXSpiYXNlWzFdWzFdKSAlIE1PRDsKICAgIG1hdFsxXVsxXSA9IChmaWJbMV1bMF0qYmFzZVswXVsxXSArIGZpYlsxXVsxXSpiYXNlWzFdWzFdKSAlIE1PRDsKICAgIGNvcHkoZmliLCBtYXQpOwp9CgpmdW5jdGlvbiBjYWxjTWF0cml4KGZpYiwgbikgewoJY29uc3QgYmFzZSA9IFtbMSwxXSwgWzEsMF1dOwoJZmliWzBdWzBdID0gMTsKCWZpYlswXVsxXSA9IDA7CglmaWJbMV1bMF0gPSAwOwoJZmliWzFdWzFdID0gMTsKCQoJd2hpbGUgKG4pIHsKCQlpZiAobiYxKSB7CgkJCW11bHRpcGx5KGZpYiwgYmFzZSk7CgkJfQoJCW11bHRpcGx5KGJhc2UsIGJhc2UpOwoJCW4gPSBuLnRvU3RyaW5nKDIpLnNsaWNlKDAsIC0xKTsKCX0KfQogCmxldCB0ID0gcGFyc2VJbnQocmVhZGxpbmUoKSk7CndoaWxlKHQtLSkKewogICAgW04sIE1dID0gcmVhZGxpbmUoKS5zcGxpdCgnICcpOwogICAgTiA9IE51bWJlcihOKTsKICAgIE0gPSBOdW1iZXIoTSk7CiAgICBsZXQgZmliID0gW1tdLFtdXTsKICAgIGNhbGNNYXRyaXgoZmliLCBOKTsKICAgIGxldCBmbiA9IGZpYlswXVsxXTsKICAgIGxldCBmbjEgPSBmaWJbMV1bMV0gOwogICAgCiAgICBjYWxjTWF0cml4KGZpYiwgTS1OKzIpOwogICAgbGV0IHN1bSA9ICAoKGZpYlswXVswXS0xKSpmbiAlIE1PRCArIChmaWJbMF1bMV0tMSkqZm4xICUgTU9EICsgTU9EKSAlIE1PRDsKICAgIHByaW50KHN1bSk7Cn0=