AT_abc295_f [ABC295F] substr = S

[problemUrl]: https://atcoder.jp/contests/abc295/tasks/abc295_f $ 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 $ 番目のテストケースに対する答えを整数として出力せよ。

### 制約 - $ 1\ \le\ T\ \le\ 1000 $ - $ S $ は数字のみからなる長さ $ 1 $ 以上 $ 16 $ 以下の文字列 - $ L,R $ は $ 1\ \le\ L\ \le\ R\