说明

有 $T$ 组数据。

每组数据你会得到一个字符串 $S$ 和两个整数 $L,R$。

我们定义 $f(i)$ 表示 $i$ 的十进制表示中有几个连续子串恰好等于 $S$。

求 $\sum_{i=L}^R f(i)$。

输入格式

第一行一个整数 $T$。

接下来 $T$ 行，每行 $3$ 个整数 $S, L, R$。

输出格式

对于每组样例，在一行中输出一个整数表示答案。

样例

6
22 23 234
0295 295 295
0 1 9999999999999999
2718 998244353 9982443530000000
869120 1234567890123456 2345678901234567
2023032520230325 1 9999999999999999

12
0
14888888888888889
12982260572545
10987664021
1

提示

$ 1\ \le\ T\ \le\ 1000 $，$S$ 的长度$1 \le |S| \le 16$。$ 1\ \le\ L\ \le\ R\ <\ 10^{16} $。