说明

Rockdu 是住在小马谷的一匹小马。他最好的朋友 Macaronlin 也住在那里。Rockdu 非常珍视友谊，以至于他与 Macaronlin 分享一切，甚至包括整数。

问题来了：如何与别人分享一个整数呢？对于一个整数 $x$，Rockdu 会将其分成两部分。具体来说，他将 $x$ 的十进制形式视为一个没有前导零的字符串，并在某个位置将其分割成两个非空子串。然后，他将这两个子串视为两个独立的十进制整数，分别记为 $x_1$（前半部分）和 $x_2$（后半部分）。

Rockdu 希望 $x_1$ 和 $x_2$ 的值尽可能接近。因此，在所有可能的分割方式中，他选择使 $x_1$ 和 $x_2$ 的绝对差最小化的那一种。例如，如果 $x = 1003$，有三种可能的分割方式：$1|003$、$10|03$ 和 $100|3$。Rockdu 选择第一种方式，因为它产生的绝对差最小：$|1 - 3| = 2$，而其他方式分别给出 $|10 - 3| = 7$ 和 $|100 - 3| = 97$。

定义 $f(x)$ 为将 $x$ 分割后得到的两个整数之间的最小绝对差。例如，$f(1003) = 2$。给定两个整数 $l$ 和 $r$，Rockdu 想要计算区间 $[l, r]$ 内所有 $i$ 的 $f(i)$ 之和。由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

• 第一行包含一个整数 $T$（$1 \le T \le 1000$），表示测试用例的数量。
• 每个测试用例在一行中包含两个整数 $l, r$（$10 \le l \le r \le 10^{18}$）。

输出格式

对于每个测试用例，在一行中输出答案对 $10^9+7$ 取模的结果。

2
108 112
114514 1919810

31
86328270

提示

对于样例中的第一个测试用例：

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

因此，$\sum_{i=108}^{112}f(i)=2+1+9+10+9=31$。

翻译由 DeepSeek V3 完成