G. Consecutive Segments
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Karel the Robot is given a string $$$S$$$ and $$$Q$$$ queries. The $$$i$$$th query consists of integers $$$L_i$$$ and $$$R_i$$$, with $$$1≤L_i≤R_i≤|S|$$$. Help Karel find the number of substrings of the same character in $$$S[L_i,R_i]$$$. For example, $$$aa$$$ contains one substring of the same character, $$$aba$$$ contains three, and $$$abbcccddaa$$$ contains five.

Input

Line 1: One string, $$$S$$$.

Line 2: One integer, $$$Q$$$.

Lines 3…$$$Q+2$$$: Line $$$i+2$$$ contains integers $$$L_i$$$ and $$$R_i$$$, separated by a space.

Output

Lines 1…$$$Q$$$: Line $$$i$$$ contains the answer to the $$$i$$$th query, more specifically the number of substrings of the same character in $$$S[L_i,R_i]$$$.

Example
Input
aabcccab
8
1 1
1 2
1 3
1 4
1 5
1 8
2 4
4 6
Output
1
1
2
3
3
5
3
1
Note

$$$1≤S≤10^5$$$

$$$1≤Q≤10^5$$$

One-indexing is used in this problem. For example, if $$$S$$$=$$$aabcccab$$$, then $$$S[3,6]$$$=$$$bccc$$$, not $$$ccca$$$.

The substrings that the inputs correspond to are $$$a$$$,$$$aa$$$,$$$aab$$$,$$$aabc$$$,$$$aabcc$$$,$$$aabcccab$$$,$$$abc$$$, and $$$ccc$$$, respectively. For instance, the answer to the $$$5$$$th query is 3 because $$$aabcc$$$ contains three substrings of the same character: $$$aa$$$, $$$b$$$, and $$$cc$$$.