3
1 3
1 4
8 10 10
10 15
1 100
2 100
100 100
15 15
99 99
50 51
2 3
3 4
4 5
2
4
68
 932
424100
424100
9026
377
6049
11074
2
3
5

f = [0]*15001
sum = [0]*15001

a = 0
b = 1
f[1] = a
f[2] = b
ct = 3
while(ct < 15001):
    c = a+b
    c %= 10000
    a = b
    b = c
    f[ct] = c
    ct += 1
for i in range(2,15001):
    sum[i] = f[i] + sum[i-1]
t = map(int,raw_input().split())
t = t[0]
for x in range(0,t):
    l,r = map(int,raw_input().split())
    ans = 0
    x = r/15000
    x = int(x)
    ans += (x*sum[15000])
    r %= 15000
    ans += sum[r]
    l -= 1
    x = l/15000
    x = int(x)
    ans -= (x*sum[15000])
    l %= 15000
    ans -= sum[l]
    print ans%1000000007