The Typewriter and Its Hidden Feature

Ali loves collecting all sorts of rare and interesting items. Recently, he discovered an old typewriter with only 28 keys: 26 lowercase letters and the letters B and P. After some investigation, he found out that the typewriter works as follows:

• When a lowercase letter is pressed, it is appended to a groove (the letter is added at the end).
• When the B key is pressed, the last letter in the groove is removed (if any exists).
• When the P key is pressed, the current content of the groove is printed on a new line (the groove remains unchanged).

For example, if the key sequence is aPaPBbP, the printed outputs are as follows:

a
aa
ab

The typewriter also has a hidden numeric keypad. By entering two numbers \(x\) and \(y\) (with \(1 \le x, y \le n\), where \(n\) is the total number of printed lines), the machine will display how many times the printed string numbered \(x\) appears as a substring in the printed string numbered \(y\). Note that overlapping occurrences are counted.

Your task is to simulate this functionality.

inputFormat

The input consists of several lines:

The first line contains a string s representing the keypress sequence. s consists of lowercase letters and the characters B and P.

The second line contains an integer q representing the number of queries.

Each of the following q lines contains two integers \(x\) and \(y\) (\(1 \le x, y \le n\)), representing a query asking for the number of times the printed string number \(x\) appears as a substring in printed string number \(y\).

outputFormat

For each query, output a single integer on a new line indicating the number of occurrences of the printed string numbered \(x\) in the printed string numbered \(y\).

sample

aPaPBbP
3
1 2
1 3
2 3

2
1
0