题目描述

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

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

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

现在定义 $f(n,R)$ 表示 $S(n)$ 中有多少个子序列满足关系串 $R$ 的限制。给定 $l,r,R$，求：

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

输入格式

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

第一行一个整数 $T$（$1\le T\le 10$），表示数据组数。

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

第二行一个关系串 $R$（$1\le \vert R\vert \le 500$），意义如题。

输出格式

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

输入样例

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

输出样例

7
5
5
4628
4377883