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

fib={}
fib[0]=0
fib[1]=1
#fib[2]=1
sum={}
sum[0]=0
sum[1]=1
#sum[2]=1
total=1
for k in range(2,15000):
	fib[k]=fib[k-1]+fib[k-2]
	sum[k]=sum[k-1]+fib[k]%10000
	#print len(fib),total
t=int(raw_input())
#print sum[14999]
for i in range(0,t):
	ans=0
	l,r=map(int,raw_input().split())
	l-=1
	r-=1
	ans=(((r-l)/15000))*sum[14999]
	l=l%15000
	r=r%15000
	if(l>r):
		ans+=sum[14999]-sum[l-1]+sum[r]
	else:
		if(l==0):
			ans+=sum[r]
		else:
			ans+=sum[r]-sum[l-1]
	print ans%1000000007