Vivek likes strings a lot but moreover he likes Awesome strings. Vivek calls a string str Awesome if zero or more letters of the string str can be rearranged to form the string "HackerEarth" (case insensitive). For eg : strings HackerEarth , Earthhacker , haeackerrth are all Awesome strings whereas strings HE, Mycareerstack , hackerrearth are not Awesome at all.
Today, Vivek has a special string consisting of both lower case and upper case alphabets letters only. Vivek wants to query this string for the number of Awesome strings.
Each of Vivek's query has the following form L R. For a given query, Vivek wants to count the number of Awesome strings such that starting index S and ending index E of the string follows L ≤ S<E ≤ R.
NOTE
Two strings are considered to be different if either S1 != S2 or E1 != E2 where S1,E1 and S2,E2 are the starting and ending index of string 1 and string 2 respectively.
Help Vivek accomplishing this task.

Input

First line of the input contains a string S denoting the Vivek's special string. Next line of the input contains a single integer Q denoting the number of Vivek's queries. Next Q lines of the input contains two integers denoting L and R respectively.

Output

For each Vivek's query, print the required answer.

Constraints

1 ≤ |S| ≤ 5x10^5

1 ≤ Q ≤ 5x10^5

1 ≤ L ≤ R ≤ |S|

S belongs to the set of both lower case and upper case alphabets letters only.
Subtask:
subtask 1 : 1 ≤ N,Q ≤ 10000 : 20 points

subtask 2 : 1 ≤ N,Q ≤ 10^5 : 20 points

subtask 3 : 1 ≤ N,Q ≤ 5x10^5 : 60 points
NOTE

large input / output data sets, be careful with some languages.

SAMPLE INPUT
HackerEarthhACKEReARTH
5
1 11
2 15
5 15
7 20
7 22

SAMPLE OUTPUT
1
4
1
4
6Explanation

Q1 : "HackerEarth" is the only awesome string.
Q2 : "ackerEarthh","ckerEarthhA","kerEarthhAC","erEarthhACK" are all awesome strings.
Q3: "erEarthhACK" is the only awesome string.
Q4: "EarthhACKER","arthhACKERe","rthhACKEReA","thhACKEReAR" are all awesome strings.
Q5: "EarthhACKER","arthhACKERe","rthhACKEReA","thhACKEReAR","hhACKEReART","hACKEReARTH" are all awesome strings.

见题面

见题面