Hasinur wants to give treat. Why? Because, he's been going out with someone new. But Hasinur doesn't want to give treat to everyone. He wants to treat only those who can answer some easy questions for him.

Hasinur will ask you N questions in total. In each question, he will give you a pair of numbers L and R. You will have to answer the sum of factorials of all numbers from L to R, modulo 1015+37 (1000000000000037). Nothing that hard ðŸ™‚.

Formally, given M and some queries in the form of L and R, you have to print the following.

$\sum_{n=L}^R n! modulo 1000000000000037$

Here, n! means the factorial of n, i.e. $n! = 1 \times 2 \times 3 \times ... \times (n-1) \times n$

Input

Input starts with two integers N (1 â‰¤ N â‰¤ 100), the number of questions.

In the next N lines, each line contains the two integers referring to a question, L (0 â‰¤ L â‰¤ 107) and R (L â‰¤ R â‰¤ 107).

Output

For each question, print the answer modulo 1015+37 in a single line.