Ali likes to collect all sorts of strange things, and he recently acquired an old-fashioned typewriter. The typewriter has only 28 keys, labeled with the 26 lowercase English letters and the two characters 'B' and 'P'.

Ali discovered that the typewriter works as follows: Inputting a lowercase letter adds that letter to a groove in the typewriter (there is at least one letter in the groove before pressing 'P'). Pressing the key labeled 'B' removes the last letter from the groove. * Pressing the key labeled 'P' prints all the letters currently in the groove onto the paper and starts a new line, but the letters in the groove do not disappear (it is guaranteed that there is at least one letter in the groove).

For example, if Ali inputs aPaPBbP, the characters printed on the paper are as follows: a aa ab

We number the strings printed on the paper sequentially starting from 1 up to $n$. The typewriter has a very interesting feature: it contains a hidden numeric keypad. By inputting two numbers $(x, y)$ (where $1 \le x, y \le n$) on this keypad, the typewriter displays how many times the $x$-th printed string appears in the $y$-th printed string.

Ali was very excited after discovering this feature and wants to write a program to perform the same task. Can you help him?

Input

The first line contains a string, representing all the characters Ali inputs in order. The second line contains an integer $m$, representing the number of queries. The next $m$ lines describe all the queries entered via the numeric keypad. The $i$-th line contains two integers $x$ and $y$, representing the $i$-th query $(x, y)$.

Output

Output $m$ lines, where the $i$-th line contains an integer representing the answer to the $i$-th query.

Examples

Input 1

aPaPBbP
3
1 2
1 3
2 3

Output 1

2
1
0

Constraints

The range and characteristics of all test data are shown in the table below: