Let us look at the close relative of Fibonacci numbers, called the Phibonacci numbers. They work exactly like Fibonacci numbers. F (1) = 0, F(1) = 1, F(2) = 1, and then F (n) = F ( n - 1 ) + F ( n - 2 ). In number theory, the n^th Pisano period, written as ? (n), is the period with which the sequence of Fibonacci numbers, modulo n repeats.

Anyway. The question is extremely simple: you're given two integers A, and B - you've to find out the sum of all the such Phibonacci numbers in the given range A and B which have no new prime divisor that does not divide any earlier Phibonacci number. For clarity and for the sake of ease, 1 is NOT considered as such a number.

Input format:
The first line contains the number of test cases. Followed by two integers A and B. Both A and B are inclusive.

Input format:
You've to print the sum of all such required numbers modulo 10^9 + 7.

Constraints:
1 ≤ Test Cases ≤ 10^3
1 ≤ B ≤ 10 ^6
1 ≤ A < B  

SAMPLE INPUT
2
6 9
12 14

SAMPLE OUTPUT
8
144

Explanation

Let's make a list of the first few Phibonacci numbers. 

0 - 1st - Not considered.
1 - 2nd - Not considered.
1 - 3rd - Not considered.
2 - 4th - 1 x 2
3 - 5th - 1 x 3
5 - 6th - 1 x 5
8 - 7th  - 2 x 2 x 2
13 - 8th - 1 x 13
21 - 9th - 3 x 7

Now, let us look at our first test case: A = 6, B = 9. Let ans = 0.
6th Phibonacci is 5 - has a new prime divisor 5. 
7th Phibonacci is 8 - has no new prime divisors. So, ans = ans + F(n).
8th Phibonacci is 13 - has a new prime divisor 13.
9th Phibonacci is 21 - has a new prime divisor 7.
t=input()
i=0
while i<t:
    x=raw_input().split(' ')
    a=int(x[0])
    b=int(x[1])
    if b<7:
        print "0"
    elif b>=7 and b<13:
        if a<=7:
            print "8"
        else:
            print "0"
    else:
        if a<=7:
            print "152"
        elif a>7 and a<=13:
            print "144"
        else:
            print "0"
    i=i+1