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

from sys import stdin
 
def convert(L, R):
    add = remove = 0
    if L % BASE != 0:
        add = BASE - (L % BASE)
    remove = R - ((R / BASE) * BASE)
 
    if add: # if add > 0
        c1 = cache[-1] - cache[(L%BASE) - 1]
    else:
        c1 = 0
   
    if remove:  # if remove > 0
        c3 = cache[remove - 1]
    else:
        c3 = 0
    print (c1 + (TOTAL * (((R-remove) - (L+add)) / BASE)) + c3) % (10**9 + 7)
 
fibs = [0, 1]  # stores fibs
digits = [fibs[-2] % 10000, fibs[-1] % 10000]  # stores the last four digits of fibs
 
for i in xrange(15000 - 2):
    x = fibs[-2] + fibs[-1]
    fibs.append(x)
    digits.append(x % 10000)
 
TOTAL = sum(digits)   # tatal sum of digits
BASE = 15000
 
cache = [0]  # our tmp array, stores the sum from start to individual index
for i in digits[1:]:
    cache.append(cache[-1] + i)
 
data = stdin
 
N = int(data.next().strip(" \n"))
for i in xrange(N):
    L, R = map(int , data.next().strip(" \n").split(" "))
    convert(L-1, R)