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

MOD=1000000007

# precalculation made in advance
# ----------------------------
# fibpairs={}
# x1=0
# x2=1
# i=1
# while not (x1,x2) in fibpairs: # hopefully num of different pairs is not high (15000)
#   fibpairs[(x1,x2)]=i
#   temp=(x1+x2)%10000
#   x1=x2
#   x2=temp
#   i+=1
# print i,fibpairs[(x1,x2)]
# -----------------------------
# after 15000 pairs we get (0,1) back
lenround=15000
dig4=10000

x1=0
x2=1
sum4=[0,1]
for i in xrange(2,lenround):
  x=(x1+x2)%dig4
  x1=x2
  x2=x
  sum4.append(sum4[-1]+x) # won't exceed MOD
roundsum=sum4[-1]

T=int(raw_input())
for iCase in xrange(T):
  l,r=map(int, raw_input().split())
  diffrounds=((r-l)/lenround)%MOD
  l=(lenround+l-2)%lenround #
  r=(lenround+r-1)%lenround
  if l<r:
    print ((diffrounds*roundsum)+sum4[r]-sum4[l])%MOD
  else:
    print ((diffrounds*roundsum)+(roundsum-sum4[l])+sum4[r])%MOD