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

per = 15000
maxn = per+10
fibo = [0]*maxn    
sumfib = [0]*maxn

fibo[1],sumfib[1] = 1,1

for i in range(2,maxn):
    fibo[i]  = (fibo[i-1]+fibo[i-2])%10000
    sumfib[i] = (sumfib[i-1]+fibo[i])

def sm(a):
    if a==0:
        return 0
    return (a/per)*sumfib[per] + sumfib[a%per]
mod = 10**9+7    
for t in range(input()):
    a,b = map(int,raw_input().split())
    a-=1
    b-=1
    print ((sm(b) - sm(a-1))%mod + mod)%mod