题目描述

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

史莱姆每天会进行占卜活动，第 $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$ 取模后的结果。

样例

输入

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

输出

45
228
3227189
64050837
32261615
188342047
329553393

对于 $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 ($5$ pts): $T \le 500, R \le 10^5$
• Subtask 2 ($10$ pts): $T \le 5, L = R \le 10^9$
• Subtask 3 ($20$ pts): $T \le 500, L = R \le 10^{12}$
• Subtask 4 ($30$ pts): $L = R$
• Subtask 5 ($10$ pts): $T \le 500, R \le 10^{12}$
• Subtask 6 ($25$ pts): 无特殊限制

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