Description

Ali likes collecting all kinds of quirky things, and he recently found an old typewriter. The typewriter has only $28$ keys, labeled with the $26$ lowercase English letters and the two letters B and P. After some study, Ali found that the typewriter works as follows:

• When a lowercase letter is entered, the letter is appended to a slot in the typewriter (this letter is added to the end of the slot).
• When the B key is pressed once, the last letter in the slot disappears.
• When the P key is pressed once, the typewriter prints all the current letters in the slot on the paper and starts a new line, but the letters in the slot remain.

For example, if Ali inputs aPaPBbP, the characters printed on the paper are:

a
aa
ab

We number the strings printed on the paper starting from $1$ up to $n$. The typewriter has a very interesting feature: it hides a numeric keypad. By entering two numbers $(x, y)$ (where $1 \leq x, y \leq n$) on the keypad, the typewriter will display how many times the $x$-th printed string appears in the $y$-th printed string.

After discovering this feature, Ali became excited and wanted to write a program to achieve the same function. Can you help him?

Input Format

The first line contains a string that lists all characters Ali inputs in order.

The second line contains an integer $m$, the number of queries.

Each of the next $m$ lines describes one query entered via the keypad. The $i$-th line contains two integers $x, y$, representing the $i$-th query $(x, y)$.

Output Format

Output $m$ lines. The $i$-th line should contain one integer, the answer to the $i$-th query.

aPaPBbP
3
1 2
1 3
2 3

2
1
0

Hint

Constraints

For $100\%$ of the testdata, $1 \leq n \leq 10^5$, $1 \leq m \leq 10^5$, and the length of the first line $\leq 10^5$.

Translated by ChatGPT 5