题目描述

Rockdu is a pony living in Ponyville. His best friend, Macaronlin, also lives there. Rockdu values friendship so much that he shares everything with Macaronlin, even integers.

Here comes the question: how to share an integer with someone else? For an integer $x$, Rockdu splits it into two parts. Specifically, he treats $x$ in decimal form as a string without leading zeros, and splits it into two non-empty substrings at a certain position. He then considers these two substrings as two separate decimal integers, denoted as $x_1$ (the former) and $x_2$ (the latter).

Rockdu wants $x_1$ and $x_2$ to be as close in value as possible. Therefore, among all possible splits, he chooses the one that minimizes the absolute difference between $x_1$ and $x_2$. For example, if $x = 1003$, there are three possible ways to split it: $1|003$, $10|03$, and $100|3$. Rockdu chooses the first way because it yields the smallest absolute difference: $|1 - 3| = 2$, whereas the other ways give $|10 - 3| = 7$ and $|100 - 3| = 97$.

Let $f(x)$ be defined as the smallest absolute difference between the two integers resulting from splitting $x$. For example, $f(1003)=2$. Given two integers $l$ and $r$, Rockdu wants to calculate the sum of $f(i)$ for all $i$ in the range $[l, r]$. Since the answer may be very large, please output it modulo $10^9 + 7$.

输入格式

The first line contains an integer $T$ ($1 \le T \le 1000$), indicating the number of test cases.

Each test case contains two integers $l,r$ ($10 \le l \le r \le 10^{18}$) in a single line.

输出格式

For each test case, output the answer modulo $10^9+7$ in a single line.

2
108 112
114514 1919810

31
86328270

提示

For the first test case in the sample:

• $f(108)=\min(|1-8|,|10-8|)=\min(7,2)=2$
• $f(109)=\min(|1-9|,|10-9|)=\min(8,1)=1$
• $f(110)=\min(|1-10|,|11-0|)=\min(9,11)=9$
• $f(111)=\min(|1-11|,|11-1|)=\min(10,10)=10$
• $f(112)=\min(|1-12|,|11-2|)=\min(11,9)=9$

Therefore, $\sum_{i=108}^{112}f(i)=2+1+9+10+9=31$.