数位的关系

Problem Description

对于一个十进制非负整数 $n$，我们可以按照从高位到低位将其写成一个由数位 $\texttt 0\sim \texttt 9$ 构成的字符串 $S(n)$（不含前导 $0$）。 称一个仅由 $\texttt <$ 和 $\texttt >$ 组成的串为关系串。对于一个长度为 $k$ 的关系串 $R=r_1r_2\cdots r_k$ 和一个长度为 $k+1$ 的字符串 $S=s_1s_2\cdots s_{k+1}$，如果任意 $1\leq i\leq k$，都有关系 $r_i(s_i,s_{i+1})$ 成立，则称字符串 $S$ 满足关系串 $R$ 的限制。 其中关系 $r_i(s_i,s_{i+1})$ 成立只有两种情况，$r_i=\texttt{<}$ 且 $s_i < s_{i+1}$ 或者 $r_i=\texttt{>}$ 且 $s_i > s_{i+1}$，比较按照字典序顺序。 现在定义 $f(n,R)$ 表示 $S(n)$ 中有多少个子序列满足关系串 $R$ 的限制。给定 $l,r,R$，求：

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

Input

本题单个测试点内包含多组测试数据。 第一行一个整数 $T(1\leq T\leq 10)$，表示数据组数。 对于每组数据，第一行两个整数 $l,r$ $(1\leq l\leq r< 10^{500})$，意义如题。 第二行一个关系串 $R$ $(1\leq |R|\leq 500)$，意义如题。

Output

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

Sample Input

5
12435 12435
<<
114514 114514
<><
1919810 1919810
<><>
1234 4321
<>
114514 1919810
<>>

Sample Output

7
5
5
4628
4377883

Source

2024“钉耙编程”中国大学生算法设计超级联赛（1）