Problem description.

Toretto has no friends. He has got family, and now they need him. His bitter enemy, Ian Shaw, has captured Toretto's beloved Letty and evil cooks in his head. All Toretto has is the algorithmic message Shaw left before leaving-
Letty(n):
    L = an empty list
    while n > 0:
        find the largest Fibonacci number f <= n
        append f to L
        n = n-f
    return L
Doing some research, Toretto finds about the Fibonacci series-
F[0] = 0; F[1] = 1 ; for each i ≥ 2: F[i] = F[i-1] + F[i-2]
But Shaw has a variation of the series which is encrypted in the above hint. Let's call it "The Letty Sequence". It's a position based sequence. The weights assigned to positions in the number are all distinct positive Fibonacci numbers, in order. For example, in the Letty Sequence, the sequence of digits 1101 represents the number 1*5 + 1*3 + 0*2 + 1*1 = 9. Some numbers have more than one representation in the Letty Sequence. For example, we can also represent 9 as 10001, because 1*8 + 0*5 + 0*3 + 0*2 + 1*1 = 9. 
To make the problem easier, Toretto now knows that the above algorithmic hint chooses one particular representation of n in Letty Sequence. For example, for n=9 we get the representation 10001 (i.e., 8+1), and for n=30 we get 1010001 (i.e., 21+8+1). 
Now Toretto needs to do this to know the location of Letty.
1. Use the above algorithmic hint to find a representation of n in Letty Sequence.
2. Take the sequence of digits obtained in step 1, and interpret it as a binary number (i.e., a number in base 2).
3. Find the decimal value of that binary number, say g(n).
For example, suppose that n=30. First, we compute that 30 in Letty Sequence is 1010001. Next, we compute that 1010001 in base 2 is 64+16+1=81. Hence, g(30)=81. 
Shaw sees all this through his acquired God's Eye technology, and gives one final hint to Toretto. he gives him two numbers- L and R, and asks for the following answer- "g(L) xor g(L+1) xor g(L+2) xor ... xor g(R-2) xor g(R-1) xor g(R))."
This is the final ride. Help the crew out, till they "See you again".
 

Input

First line contains T, the number of test cases. T lines follow.
Each line contains two space seperated integers- L and R.


Output
Output the required answer MODULO 1000000007.

Constraints

R will be between 1 and 10^15, inclusive.
L will be between 1 and B, inclusive.

Example
Input:
2
1 2
3 10



Output:

3
25
 

Explanation

TC 1: We have g(1)=1, g(2)=2, and (1 xor 2)=3.
TC 2:
Shaw's hint chooses the following Letty Sequence representations for the numbers 3 through 10:
00100 
00101 
01000 
01001 
01010 
10000 
10001 
10010 
If we consider these as base-2 numbers, their values are 4, 5, 8, 9, 10, 16, 17, and 18. Thus, the answer is (4 xor 5 xor 8 xor ... xor 18) = 25.
.
import sys
f = sys.stdin

mod = 1000000007
DP = [0]*(2)
DP[0] = [0]*(111)
DP[1] = [0]*(111)
bits = [0]*(111)
X = [0]*(2)
Y = [0]*(2)
X[0] = [0]*(111)
X[1] = [0]*(111)
Y[0] = [0]*(111)
Y[1] = [0]*(111)
def process():
    DP[0][100] = 1
    DP[1][100] = 1
    X[0][100] = 1
    Y[0][100] = 0
    Y[1][100] = 1
    X[1][100] = 0
    i = 99
    while i >= 0 :
        DP[0][i] = DP[0][i+1] + DP[1][i+1]
        DP[1][i] = DP[0][i+1]
        X[0][i] = X[0][i+1] + X[1][i+1]
        Y[0][i] = Y[0][i+1] + Y[1][i+1]
        X[1][i] = X[0][i+1]
        Y[1][i] = Y[0][i+1]
        i -= 1
    return

def find(x) :
    for i in range(0,101) :
        if x > DP[0][i] :
            bits[i] += x - DP[0][i]
            x -= DP[0][i]
            j = 100
            k = i  
            while j > i :
                bits[j] += Y[0][k] * DP[1][j]
                k += 1 
                j -= 1
    return

t = int(f.readline())
process()
while t :
    L,R = [int(x) for x in f.readline().split()]
    R += 1
    for i in range(0,101) :
        bits[i] = 0
    find(R)
    find(L)
    sum = 0
    for i in range(0,101) :
        bits[i] %= 2
        if bits[i] == 1 :
            sum += pow(2,100-i,mod)
            sum %= mod
    print sum
    t -= 1