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\le x\le r$ (mod ${10}^9+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\le x\le r$ (mod ${10}^9+7$).

Constraints:
$1\le T\le {10}^5$
$1\le l\le r\le {10}^{18}$