QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 2048 MB Total points: 100

# 4904. 圆滚滚的算术占卜

统计

在具有高度智慧的、拥有“史莱姆的导师”之称的红头史莱姆的引导下,史莱姆们理解了十进制数,并能够利用数字进行占卜。

史莱姆每天会进行占卜活动,第 $k$ 天的流程如下:

  1. 将 $n$ 的值设为 $k$ 。
  2. 将 $n$ 的不含前导0的十进制表示写下来。如果现在已经写下来了一些数,就将 $n$ 写在它们的后面。
  3. 令 $n:=n-S(n)$ ,其中 $S(n)$ 表示 $n$ 的十进制表示的各位数字之和,例如 $S(233)=2+3+3=8$ ,$S(114514)=1+1+4+5+1+4=16$ 。
  4. 如果 $n=0$,结束占卜,否则回到第2步。

最终的占卜结果是一个十进制数字串。显然,它也表示了一个十进制数。史莱姆想让你帮它们求出,第 $L$ 天到第 $R$ 天的占卜结果之和是多少。由于答案可能很大,你只需要求出对 $998244353$ 取模后的结果。史莱姆们总共问了 $T$ 个这样的问题,你需要对每个问题求出答案。

输入格式

第一行包含一个正整数 $T$ ,表示史莱姆的问题个数。

接下来 $T$ 行,每行两个正整数 $L$ 和 $R$ ,表示你需要求出第 $L$ 天到第 $R$ 天的占卜结果之和。

输出格式

对于每组询问,输出答案对 $998244353$ 取模后的结果。

样例

input

7
1 9
10 11
32 32
16058 258258
1 998244353
31415926 271828182
757427636498525616 1000000000000000000

output

45
228
3227189
64050837
32261615
188342047
329553393

explanation

对于 $1\le k\le 9$,第 $k$ 天的占卜一次就会结束,因此占卜结果就是 $k$ ,第一组询问的答案为 $1+2+3+\dots+9=45$ 。

第 $10$ 天的占卜中会依次写下 $10$ 和 $10-S(10)=9$ ,第 $11$ 天会依次写下 $11$ 和 $9$ ,从而第二组询问的答案为 $109+119=228$ 。

第 $32$ 天会依次写下 $32$ ,$32-S(32)=27$ ,$27-S(27)=18$ 和 $18-S(18)=9$ ,因此第三组询问的答案是 $3227189$ 。

限制与约定

Subtask 1(5pts): $T\le 500,R\le 10^5$ 。

Subtask 2(10pts): $T\le 5,L=R\le 10^9$ 。

Subtask 3(20pts): $T\le 500,L=R\le 10^{12}$ 。

Subtask 4(30pts): $L=R$ 。

Subtask 5(10pts): $T\le 500,R\le 10^{12}$ 。

Subtask 6(25pts): 无特殊限制。

对于所有测试数据,满足 $1\le T\le 5\times 10^4,1\le L\le R\le 10^{18}$ 。

时间限制:$4\texttt{s}$

空间限制:$2\texttt{GB}$