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:
		c1 = cache[-1] - cache[(L%BASE) - 1]
	else:
		c1 = 0
	
	if remove:
		c3 = cache[remove - 1]
	else:
		c3 = 0
	print (c1 + (TOTAL * (((R-remove) - (L+add)) / BASE)) + c3) % (10**9 + 7)

fibs = [0, 1]
digits = [fibs[-2] % 10000, fibs[-1] % 10000]
for i in xrange(15000 - 2):
	x = fibs[-2] + fibs[-1]
	fibs.append(x)
	digits.append(x % 10000)

TOTAL = sum(digits)
BASE = 15000

cache = [0]
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)