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 15 + 13 + 02 + 11 = 9. Some numbers have more than one representation in the Letty Sequence. For example, we can also represent 9 as 10001, because 18 + 05 + 03 + 02 + 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.
.

见题面

见题面