Sum of Digits Range

You are given T test cases. In each test case, you are given two integers L and R (with 1 ≤ L ≤ R ≤ 10¹⁸). For each test case, compute the sum of the digit sums for every integer in the inclusive range [L, R]. Since the answer can be very large, output the result modulo 10⁹+7.

The digit sum of a number is defined as the sum of its digits. For example, the digit sum of 123 is 1+2+3 = 6.

Input Constraints:

• 1 ≤ T ≤ 20
• 1 ≤ L ≤ R ≤ 10¹⁸

Your task is to write a program to solve Mr.G's modified homework problem.

inputFormat

The first line contains an integer T, the number of test cases.

Each of the next T lines contains two space‐separated integers L and R.

outputFormat

For each test case, output a single line with the sum of the digit sums of all numbers in the range [L, R] modulo 10⁹+7.

sample

3
1 10
100 111
1 100

46
60
901