当前没有测试数据。

F - substr = S

分数 : $500$ 分

题目描述

对于每个测试样例，给定一个由数字和正整数组成的字符串 $S$，以及正整数 $L$ 和 $R$。解决以下问题。

对于正整数 $x$，定义 $f(x)$ 为 $x$ 的十进制表示的连续子串（没有前导零）的数量，这些子串等于 $S$。

例如，如果 $S=$ 22，我们有 $f(122) = 1$，$f(123) = 0$，$f(226) = 1$ 和 $f(222) = 2$。

计算 $\displaystyle \sum_{k=L}^{R} f(k)$。

约束

• $1 \le T \le 1000$
• $S$ 是一个由数字组成的字符串，长度在 $1$ 到 $16$ 之间。
• $L$ 和 $R$ 是满足 $1 \le L \le R < 10^{16}$ 的整数。

---

输入

输入数据是标准输入格式，具体格式如下，其中 $\rm{case}_i$ 表示第 $i$ 个测试样例：

$T$

$\rm{case}_{1}$

$\rm{case}_{2}$

$\vdots$

$\rm{case}_{\it{T}}$

每个测试样例的格式如下：

``` $S$ $L$ $R$ ```

输出

一共输出 $T$ 行。
第 $i$ 行包含一个整数，表示第 $i$ 个测试样例的答案。

---

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

这个样例一共有六个测试样例。

• 第一个测试样例中，$S=$ 22，$L=23$，$R=234$。
  • $f(122)=f(220)=f(221)=f(223)=f(224)=\dots=f(229)=1$。
  • $f(222)=2$。
  • 因此，答案是 $12$。
• 第二个测试样例中，$S=$ 0295，$L=295$，$R=295$。
  • 注意到 $f(295)=0$。