H. Friendship is Magic
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

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$$$.

Input

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.

Output

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

Example
Input
2
108 112
114514 1919810
Output
31
86328270
Note

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$$$.