Migrated from Lutece 2577 随机数掌握在我手中

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

这天，你在梦中参透了某手游使用的抽卡算法：当有抽卡请求到来时，首先获取当前时间戳 $t$，然后判断 $t$ 的十进制表示是否含有你的 ID $135$ 或版本答案 $42$。如果至少含有其中一项，则返回一个六星干员。比如，$t=13589270$，则出货；$t=2018091612345$，则无事发生。

然而知道了抽卡的算法并不足以让你一发出货，由于网络延迟等不稳定因素，你只能预计，当你的抽卡请求到达服务器时，$t\in [l,r]$，而不能精确控制 $t$ 的值。退而求其次，你可以计算 $t$ 的可能取值区间 $[l,r]$ 中，有多少个时间戳包含 $135$ 或 $42$ 的，如果数量较多，出货概率会比较大，这样也好。

现在你打算制定抽卡计划。你想了 $n$ 个你有兴趣抽卡的时间，并估计出了请求到达服务器时的时间区间，计算这些区间内能出货的时间戳个数。由于这个数可能很大，请将它对 $998244353$ 取模。

TL，DR：回答 $n$ 个询问，每次询问区间 $[l,r]$ 中包含 $135$ 或 $42$ 的数字个数，结果对 $998244353$ 取模。

Input

第一行输入一个整数 $n\ (1\le n \le 100)$，表示你想了 $n$ 个有兴趣抽卡的时间。

接下来的 $n$ 行，每行输入两个整数 $l,r$，表示 $t\in [l,r]\ (0\le l,r\le 10^{1000})$。

Output

输出 $n$ 个整数 $a_1,a_2,\ldots ,a_n$，表示在第 $i$ 个给定区间中，能出货的时间戳有 $a_i$ 个。每个整数占一行。

Samples

3
1 42
1 135
42 135

1
2
2

1
20001104 20210522

9828

Resources

2021 UESTC ICPC Training for Dynamic Programming