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

def Fib(m):
	global dp
	if len(dp)>m:
		return None
	else:
		i=len(dp)
		while i<m:
			temp=dp[i-1]+dp[i-2]
			dp.append(temp%10000)
			i+=1
dp=[0,1,1]
Fib(15000)
sums=[0]
for i in xrange(1,15000):
	sums.append(sums[i-1]+dp[i])
T=int(raw_input().strip())
for _ in xrange(T):
	n,m=raw_input().strip().split(' ')
	n,m=int(n),int(m)-1
	if n<2:
		print (sums[14999]*((m)/15000)+sums[(m)%15000])%(10**9+7)
	else:
		n=n-2
		print (sums[14999]*((m)/15000)+sums[(m)%15000]-sums[14999]*(n/15000)-sums[n%15000])%(10**9+7)