时空限制

1S/512M

题目描述

称数字 $X$ 从低位到高位的第 $i$ 个数位为 $X_i$，例如对于 $X=420$，有 $X_1=0$，$X_2=2$，$X_3=4$。

记数字 $X$ 的数位共有 $len(X)$ 个，如果 $X$ 满足以下两个条件中的任意一条，称 $X$ 为波浪数：

• 对于满足 $1<i\leq len(X)$ 的任意偶数 $i$，有 $X_{i-1}>X_i$ 且当 $i< len(X)$ 时还有 $X_i<X_{i+1}$；
• 对于满足 $1<i\leq len(X)$ 的任意偶数 $i$，有 $X_{i-1}<X_i$ 且当 $i< len(X)$ 时还有 $X_i>X_{i+1}$；

例如：$13$ 满足第一条条件，$15240$ 满足第二条条件，$4$ 同时满足两条条件，$13212$ 不满足任意一条。因此 $13,15240,4$ 都是波浪数，而 $13212$ 不是波浪数。

有 $q$ 个询问，第 $i$ 个询问求 $L_i\sim R_i$ 中有多少个波浪数，对 $998244353$ 取模。

格式

输入格式

第一行包含一个整数 $q$ 表示询问的数量。

接下来 $q$ 行每行包含两个整数 $L_i,R_i$，表示一个询问。

输出格式

输出 $q$ 行，每行一个整数，第 $i$ 个整数为第 $i$ 个询问的答案。对 $998244353$ 取模。

样例

样例输入 #1

1
84 122

样例输出 #1

25

样例解释 #1

$84\sim 122$ 中有以下 $25$ 个波浪数：$84$、$85$、$86$、$87$、$89$、$90$、$91$、$92$、$93$、$94$、$95$、$96$、$97$、$98$、$101$、$102$、$103$、$104$、$105$、$106$、$107$、$108$、$109$、$120$、$121$。

样例输入 #2

2
23456 65432
1234567 7654321

样例输出 #2

9570
520892

数据规模

对于 $30\%$ 的数据，$R_i\leq 10^7$。

另有 $30\%$ 的数据，$L_i=1$。

对于 $100\%$ 的数据，$1\leq q\leq 10$，$1\leq L_i\leq R_i\leq 10^{100000}$。