National Olympiad in Informatics, China, 2011

Ali likes to collect all kinds of strange gadgets. Most recently, he's gotten his hands on an old-fashioned typewriter. The typewriter contains $28$ keys, $26$ of which are the lowercase alphabet, and the other $2$ are the uppercase letters B and P.

Through further examination, Ali learned that the typewriter worked like this:

• Hitting a lowercase letter, the typewriter will append this letter onto a special groove. There will be at least one such letter before hitting P.
• Hitting the B key, the typewriter will remove the last letter added to the groove.
• Hitting the P key, the typewriter will take all the letters currently on the groove and print them onto the paper, switching lines afterwards. However, the letters on the groove will not disappear nor change. There will be at least one letter on the groove for this operation.

For example, if Ali hits the keys aPaPBbP, then the following will be printed onto the paper:

a
aa
ab

We number the strings printed onto the paper from $1$ to $n$. The typewriter has a very interesting feature – there exists a hidden numerical keypad where, if one were to input two numbers $(x,y)$ (for $1\le x,y\le n$) the typewriter will display the number of times the $x$-th string appears in the $y$-th string.

Ali is very excited after discovering this feature. He wants to write a program to perform the exact same feature. Can you help him?

Input Specification

The first line contains a single string, describing all of the keys that Ali presses on the typewriter.
The second line contains a single integer $m$, representing the number of queries.
For the following $m$ lines, each line will describe a query on the hidden numerical keypad. The $i$-th of these lines contains two integers $x$ and $y$, indicating that the $i$-th query is $(x,y)$.

Output Specification

Output $m$ lines, where the $i$-th line contains a single integer – the answer to the $i$-th query.

Sample Input

aPaPBbP
3
1 2
1 3
2 3

Sample Output

2
1
0

Constraints

The attributes of all the test cases are outlined below.

Test Case	Range of $n$	Range of $m$	Length of Strings	Keypresses (Line $1$ of input)
$1$	$1\le n\le 100$	$1\le m\le 1000$	/	$\le 100$
$2$
$3$	$1\le n\le 1000$	$1\le m\le {10}^4$	Individual lengths $\le 1000$ Total length $\le {10}^5$	$\le {10}^5$
$4$
$5$	$1\le n\le {10}^4$	$1\le m\le {10}^5$	Total length $\le {10}^5$
$6$
$7$
$8$	$1\le n\le {10}^5$	$1\le m\le {10}^5$	/
$9$
$10$

Problem translated to English by Alex.