| A - Fibonacci Sum |
A Fibonacci sequence is calculated by adding the previous two members of the sequence, with the first two members being both 1.
f (1) = 1; f (2) = 1; f (n > 2) = f (n - 1) + f (n - 2)
We define a special fibonacci sequence where the maximum value in the sequence is 99. If a value in the sequence is greater than 99, a module 100 operation must be applied. The result is the following sequence:
1 1 2 3 5 8 13 21 34 55 89 44 33 77 10 87 97 84 81 65 ...
Your task is to calculate the sum of the numbers in this special fibonacci sequence between two given positions.
The input will contain several test cases. The first line indicates the number of test cases.
For each test case, the first line contains two integers: N and M (N ≤ M). N is the position of the first number that you should sum, and M is the position of the last number that you should sum. M is not greater than 1012.
For each test case, you have to output the result of the sum in a different line.
4
1 3
4 4
5 100
1 99999
4
3
5068
4933400
OMP'13
Facultad
de Informatica
Universidad
de Murcia (SPAIN)