Background

The very capable Little A was chosen as the problem setter for ION2018, and now he needs to solve the problem of naming the tasks.

Problem Description

Little A was chosen as the problem setter for ION2018. He carefully prepared a very high-quality problem, and has already finished all the work except naming the problem.

Since ION has been held for many years, there are also rules for naming problems. The ION problem-setting manual states: every year, the problem committee specifies a lowercase-letter string, which we call that year's naming string. The name of each problem must be a non-empty contiguous substring of that year's naming string, and it must not be the same as the name of any problem in the previous year.

For some special reasons, Little A does not know the names of each problem in ION2017, but through some special means he obtained the ION2017 naming string. Now Little A has $Q$ queries: each time, given the ION2017 naming string and the ION2018 naming string, find how many possible problem names are guaranteed to satisfy the committee's rules, that is, the name is a non-empty contiguous substring of the ION2018 naming string and is guaranteed not to be the same as the name of any problem in ION2017.

For some special reasons, in all queries, the given ION2017 naming strings are contiguous substrings of some string. See the input format for details.

Input Format

The first line contains a string $S$. In the queries below, the given ION2017 naming string is always a contiguous substring of $S$. The second line contains a positive integer $Q$, indicating the number of queries. The next $Q$ lines each contain a string $T$ and two positive integers $l, r$, meaning: if the ION2017 naming string is $S_{l\ldots r}$ and the ION2018 naming string is $T$, then how many naming choices are guaranteed to satisfy the rules.

Output Format

Output $Q$ lines. The $i$-th line contains a non-negative integer, representing the answer to the $i$-th query.

scbamgepe
3
smape 2 7
sbape 3 8
sgepe 1 9

12
10
4

Hint

More Samples

Please download more samples from the additional files.

Sample 2

See name2.in and name2.ans in the additional files.

Constraints

::cute-table{tuack}

For all data, it is guaranteed that $1\leq l \leq r \leq |S|$, $1\leq |T|\leq 5 \times 10^5$.

Thanks to @Wen_kr for providing a set of hack testdata.

Translated by ChatGPT 5