実力のある小 A は ION2018 の出題者に選ばれ、今は問題の名前を決める必要があります。

問題文

小 A は ION2018 の出題者に選ばれ、質の非常に高い問題を丹念に準備しました。問題に名前を付ける以外の作業は、すでにすべて終わっています。

ION はすでに何度も開催されているので、問題の名前にも規則があります。ION の出題マニュアルでは、毎年、出題委員会が英小文字からなる文字列を 1 つ定め、その年の命名文字列と呼ぶとしています。各問題の名前は、その年の命名文字列の空でない連続部分文字列でなければならず、前年のどの問題の名前とも同じであってはなりません。

ある特別な理由により、小 A は ION2017 の各問題の名前を知りません。しかし、特別な手段を使って ION2017 の命名文字列を入手しました。小 A には $Q$ 個の質問があります。各質問では、ION2017 と ION2018 の命名文字列が与えられます。出題委員会の規則を必ず満たす問題名が何通りあるかを求めてください。すなわち、ION2018 の命名文字列の空でない連続部分文字列であり、ION2017 のどの問題の名前とも確実に異なる名前の個数です。

ある特別な理由により、すべての質問で与えられる ION2017 の命名文字列は、ある文字列の連続部分文字列です。詳細は入力を参照してください。

入力

最初の行には文字列 $S$ が 1 つ与えられます。以降の質問で与えられる ION2017 の命名文字列は、すべて $S$ の連続部分文字列です。

2 行目には、質問の個数を表す正整数 $Q$ が 1 つ与えられます。

続く $Q$ 行には、それぞれ文字列 $T$ と 2 つの正整数 $l,r$ が与えられます。ION2017 の命名文字列が $S[l..r]$、ION2018 の命名文字列が $T$ であるとき、必ず規則を満たす命名方法が何通りあるかを問います。

入力中の文字列は、すべて英小文字からなることが保証されます。

出力

$Q$ 行出力してください。$i$ 行目には、$i$ 番目の質問の答えを表す非負整数を 1 つ出力してください。

入出力例

入力 1

scbamgepe
3
smape 2 7
sbape 3 8
sgepe 1 9

出力 1

12
10
4

入出力例 2

選手用ディレクトリ内の name/name2.in と name/name2.ans を参照してください。

小課題

すべてのデータについて、$1\le l\le r\le \lvert S\rvert,\ 1\le \lvert T\rvert\le 5\times 10^5$ が保証されます。