Little Shino loves to play with numbers. She just came to know about Fibonacci Series.
Fibonacci Series is a series of number such that
Fib(1)=0
Fib(2)=1
Fib(x)=Fib(x−1)+Fib(x−2)where2<x
Soon Little Shino realized that Fibonacci series grows very fast. So she just wants the sum of last 4 digits of the Fib(x) where l≤x≤r (mod 109+7) . Can you help her.
Input:
First line of each test case contains one integer, T, number of test cases.
Each test case contains two integer, l and r.
Output:
Print the sum of last 4 digits of the Fib(x) where l≤x≤r (mod 109+7).
Constraints:
1≤T≤105
1≤l≤r≤1018
Fib(1)=0
Fib(2)=1
Fib(3)=1
Fib(4)=2
Fib(8)=13
Fib(9)=21
Fib(10)=34
First case:
Sum of last 4 digits of Fib(1),Fib(2) and Fib(3) is 2.
Second case:
Sum of last 4 digits of Fib(1),Fib(2),Fib(3) and Fib(4) is 4.
Third case:
Sum of last 4 digits of Fib(8),Fib(9) and Fib(10) is (0013+0021+0034) (mod 109+7) = 68
