对于一个十进制非负整数 $n$，我们可以按照从高位到低位将其写成一个由数位 $0~9$ 构成的字符串 $S(n)$（不含前导 $0$）。

称一个仅由 < 和 > 组成的串为关系串。对于一个长度为 $k$ 的关系串 $R=r_1r_2 \dots r_k$ 和一个长度为 $k+1$ 的字符串 $S=s_1s_2\dots s_{k+1}$，如果任意 $1 ≤ i ≤ k$，都有关系 $r_i(s_i,s_{i+1})$ 成立，则称字符串 $S$ 满足关系串 $R$ 的限制。

其中关系 $r_i(s_i,s_{i+1})$ 成立只有两种情况，$r_i=\lt$ 且 $s_i \lt s_{i+1}$ 或者 $r_i=\gt$ 且 $s_i \gt s_{i+1}$，比较按照字典序顺序。

现在定义 $f(n,R)$ 表示 $S(n)$ 中有多少个子序列满足关系串 $R$ 的限制。给定 $l,r,R$，求：
$(∑_{n=l}^rf(n,R))\ mod\ 998244353$

其中一个字符串的子序列定义为从原字符串中删去若干个（可以不删或删空）字符得到的新字符串。

本题单个测试点内包含多组测试数据。

第一行一个整数 $T(1 ≤ T ≤ 10)$，表示数据组数。

对于每组数据，第一行两个整数 $l,r (1 ≤ l ≤ r \lt 10^{500})$，意义如题。

第二行一个关系串 $R (1 ≤ |R| ≤ 500)$，意义如题。

对于每组数据输出 $q$ 行，每行一个整数表示答案。