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 想要计算所有 $i \in [l, r]$ 的 $f(i)$ 之和。由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

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

输出格式

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

样例

样例输入 1

2
108 112
114514 1919810

样例输出 1

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