配点 : $500$ 点

問題文

$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)$ を求めてください。

制約

• $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

この入力には $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$ です。
• $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$ となることに注意してください。
• $f(295)=0$ となることに注意してください。