题目描述

下载

小 Q 在玩一个经典游戏。他面前写着一个由 $0\sim 9$ 组成的数字串，他需要在每个数字前加一个 $+$ 或 $-$（包含第一个数字），得到一个加减法算式。他希望最小化这个算式结果的绝对值。

但这个游戏对他来说太简单了，他现在写下了 $[l,r]$ 内所有正整数，没有前导零。他希望计算出以每个 $l\le i\le r$ 作为数字串玩上面的游戏，得到的结果是什么，记作 $f(i)$。由于 $r-l+1$ 可能很大，你只需要对每个 $m$，输出 $\sum_{l\le i\le r} [f(i)=m]i$ 的结果，即所有答案为 $m$ 的数之和，对 $10^9+7$ 取模。可以证明 $f(i)\in [0,9]$，所以你需要输出 $10$ 个整数，依次表示 $m=0,1,\cdots,9$ 时的和。

小 Q 一共进行了 $T$ 次上述过程，你需要对每一次都求出答案。

输入格式

第一行一个正整数 $T$，表示测试数据组数。

对于每组数据，一行两个正整数 $l,r$，表示查询区间。

输出格式

对于每组数据，输出一行 $10$ 个整数 $a_0,a_1,\cdots,a_9$，其中 $a_m$ 表示 $m$ 的答案。

样例

样例 1 输入

7
1 10
11 50
51 100
101 500
501 1000
19260817 19260818
1234567890123456789 1234567890987654321

样例 1 输出

0 11 2 3 4 5 6 7 8 9
110 210 211 193 166 180 84 47 19 0
385 770 579 497 424 310 306 243 171 90
19080 34666 27312 19047 10615 5490 2594 1097 299 0
43695 81005 67134 55962 46289 35085 23872 13924 6385 1899
19260817 19260818 0 0 0 0 0 0 0 0
230833519 749351908 0 0 0 0 0 0 0 0

附加样例

见下发文件，第 $i$ 组下发样例符合第 $i$ 个子任务的限制。

数据范围与约定

对于全部数据，$1\le T\le 10^4,1\le l\le r<10^{100}$。