P12770 [HackerEarth] mozart numbers
普及
题目描述

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.

输入格式

见题面

输出格式

见题面

样例输入
200 2 14 17 24 12 19 17 18 2 17 3 6 1 5 13 14 17 18 1 2 1 2 10 30 1 13 4 7 22 24 9 24 5 26 21 22 4 7 13 15 1 2 6 10 16 25 1 6 3 14 1 12 10 15 7 11 5 8 1 8 5 16 5 7 11 24 1 12 7 8 5 30 12 25 4 14 4 12 13 18 18 27 7 11 2 10 8 19 2 20 15 19 5 14 17 30 4 14 2 30 2 4 16 21 7 14 15 26 2 22 6 9 3 17 2 29 9 15 10 19 11 27 12 30 1 16 6 14 3 4 10 19 13 23 9 11 1 11 5 15 5 14 10 26 17 28 13 22 12 17 5 22 18 30 2 27 1 4 2 22 15 22 3 9 8 26 2 23 4 8 2 9 11 30 1 3 4 5 1 17 13 18 5 14 17 19 7 10 5 13 7 24 9 18 5 10 1 2 2 3 3 24 17 24 1 2 2 4 12 16 17 28 6 13 16 19 1 16 5 9 5 12 2 5 1 4 9 11 3 10 2 4 5 16 11 24 20 21 23 30 4 21 2 3 1 9 1 15 8 14 6 11 5 24 3 6 1 12 4 19 1 12 2 4 17 23 2 3 2 11 4 19 13 20 7 20 1 7 23 28 8 9 1 2 21 30 1 2 1 7 2 3 10 13 3 12 24 26 4 5 2 8 11 12 9 10 3 11 6 8 13 26 3 19 4 18 1 13 1 5 18 24 5 6 5 12 6 7 8 15 14 17 6 10 9 26 6 11 3 9 6 7 12 15 2 6 19 30 1 4 8 9 29 30 4 7 5 14 6 26 12 13 5 8 1 2 21 22 1 21 5 15 3 5 1 8 3 6 4 8 15 27 3 29 13 25 7 16 15 18 4 12 11 17 3 24 10 14 1 8
样例输出
152 0 144 0 152 0 0 144 0 0 0 144 152 8 0 144 152 0 8 144 0 8 0 0 152 8 144 8 8 8 152 8 144 8 8 152 144 152 8 144 0 8 8 144 152 0 152 0 152 152 0 0 152 0 152 8 152 152 144 144 144 144 152 152 0 144 144 0 8 152 152 144 0 144 144 152 0 152 0 152 0 8 144 152 8 8 144 0 0 152 144 152 0 8 152 152 144 8 0 0 152 0 0 0 144 0 152 0 152 8 8 0 0 0 8 0 152 144 0 0 152 0 8 152 144 8 152 0 8 152 8 0 0 0 8 152 144 152 8 0 0 0 0 0 8 0 144 8 0 0 8 0 0 8 8 144 152 152 152 0 0 0 8 8 144 0 8 144 8 8 8 144 0 0 0 0 0 8 152 152 144 8 0 0 152 152 0 8 0 8 0 152 144 152 0 8 144 152 144 8