题目描述

$T$ 個のテストケースについて、数字のみからなる文字列 $S$ と正整数 $L,R$ が与えられるので、以下の問題を解いてください。

正整数 $x$ に対して $f(x)=$ ( $x$ を ( 先頭に $0$ を含まないように ) 書き下した文字列の連続部分列のうち $S$ と合致するものの個数 ) と定義します。

例えば $S=$ 22 であるとき、$ f(122)\ =\ 1,\ f(123)\ =\ 0,\ f(226)\ =\ 1,\ f(222)\ =\ 2 $ となります。

このとき、 $\displaystyle\ \sum_{k=L}^{R}\ f(k)$ を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。$\rm{case}_i$ は $i$ 個目のテストケースを表す。

$T$ $\rm{case}_{1}$ $\rm{case}_{2}$ $\vdots$ $\rm{case}_{\it{T}}$

各テストケースは以下の形式である。

$S$ $L$ $R$

输出格式

全体で $T$ 行出力せよ。
そのうち $i$ 行目には $i$ 番目のテストケースに対する答えを整数として出力せよ。

题目大意

有 $T$ 组数据。

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

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

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

Translated by Tx_Lcy

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$ 以上 $16$ 以下の文字列
• $L,R$ は $1\ \le\ L\ \le\ R\ <\ 10^{16}$ を満たす整数

Sample Explanation 1

この入力には $6$ 個のテストケースが含まれます。 - $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$ です。 - $2$ つ目のケースは $S=$ 0295 $,L=295,R=295$ です。 - $f(295)=0$ となることに注意してください。