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⁹ + 7.

Constraints:
1 <= Test Cases <= 10³
1 <= B <= 10 ⁶
1 <= A < B