题目描述

我们是守护者，也是一群时刻对抗着危险和疯狂的可怜虫。---$Dunn Smith$

作为一名值夜者，克莱恩常常解读罗塞尔大帝的日记。

罗塞尔大帝高考分数没上二本线，他数学很差。因此他的日记里采用了一种特殊的方式表示区间。

比如说给定区间 $[l,r]$，罗塞尔大帝会用 $[l,r]$ 内所有数数位之和来表示这个区间。

现在给定你若干对 $l$ 和 $r$，问它们在罗塞尔大帝的日记里表示为多少。

由于罗塞尔大帝扭曲了日记的真实内容，你只需要将结果模上 $10^9+7$。

输入格式

第一行一个正整数 $q$，表示询问次数。
接下来 $q$ 行，每行两个正整数 $l$ 和 $r$，表示询问区间。

输出格式

对于每个询问分别输出一行。

3
1 6
3 9
4 11

21
42
42

数据范围与提示

共 $20$ 个测试点。
对于 $20\%$ 的数据，有 $q\leq 10^3$，$1\leq l\leq r\leq 2\times 10^9$，$r-l\leq 10^3$。
对于另外 $20\%$ 的数据，有 $q\leq 10^5$，$1\leq l\leq r\leq 10^5$。
对于 $100\%$ 的数据，有 $1\leq q\leq 10^5$，$1\leq l\leq r\leq 2\times 10^9$。