Count Substring Occurrences

You are given a string s and several queries. Each query is composed of three parts: two integers l and r which denote the 1-indexed starting and ending positions, and a substring sub. Your task is to determine the number of times sub appears (including overlapping occurrences) within the substring of s from index l to r (both ends inclusive).

For example, with s = "aaa" and the query (1, 3, "aa"), the answer is 2 because "aa" appears in "aaa" starting at positions 1 and 2.

inputFormat

The input is read from standard input (stdin).

The first line contains the string s. The second line contains an integer q representing the number of queries. Each of the following q lines contains two integers l and r followed by the substring sub (a non-empty string without spaces), separated by spaces.

outputFormat

For each query, output an integer on a new line representing the number of times sub occurs (including overlapping occurrences) within the specified segment of s.## sample

abcabcabc
3
1 3 abc
1 6 abc
2 9 bc

1
2
3