Alice、Bob 和 Eve 正在玩一种纸上游戏。每当 Eve 展示一个自然数时，Alice 和 Bob 就会在各自的纸上写下这个数字（十进制表示），在每个数字前加上加号或减号，然后计算他们各自写出的算术表达式的值。绝对值较小的人获胜。如果他们的绝对值相同，则视为平局，他们需要再玩一次。

实际上，如果他们足够聪明，游戏将永远不会结束。因此过了一段时间，他们转而关注这个谜题的最优解。令 $f(m)$ 为由 $m$ 的数字所能构成的算术表达式的最小绝对值。他们想知道你是否能帮助他们确定对于每个满足 $l \le m \le r$ 的整数 $m$ 的 $f(m)$。

等等。在意识到你完美的编程技巧后，他们决定也为你出一个谜题。他们为你设置了若干个问题 $(l, r)$，你的任务是找出所有满足 $l \le m \le r$ 且 $f(m) = k$ 的整数 $m$ 的和，其中 $k = 0, 1, 2, \dots, 9$，并将结果对 $(10^9 + 7)$ 取模。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^4$)，表示问题的数量。 接下来的 $n$ 行，每行包含两个整数 $l$ 和 $r$ ($1 \le l \le r \le 10^{100}$)，表示一个问题。

输出格式

对于每个问题，在一行中输出十个以空格分隔的整数，其中第 $i$ 个整数表示满足 $l \le m \le r$ 且 $f(m) = i$ 的所有整数 $m$ 的和，对 $(10^9 + 7)$ 取模。

样例

输入 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

说明

$19260817$ 的十进制数字为 $\{1, 9, 2, 6, 0, 8, 1, 7\}$，可以构建算术表达式 $(+1 - 9 - 2 - 6 + 0 + 8 + 1 + 7)$，其值为 $0$，绝对值为 $0$。

$19260818$ 的十进制数字为 $\{1, 9, 2, 6, 0, 8, 1, 8\}$，可以构建算术表达式 $(+1 - 9 + 2 + 6 - 0 - 8 - 1 + 8)$，其值为 $-1$，绝对值为 $1$。