Chef likes strings a lot but moreover he likes good strings. Chef calls a string str a good string if str starts and ends at different characters. For eg : strings such as abab , baccba , abc are all good strings whereas strings like aba, baab , baacaab are not good at all .
Today, Chef has a special string P consisting of lower case letters "c" , "h" , "e" and "f" only. Chef wants to make some queries about his string P.
Each of chef's query has the following form a b L R. For a given query, Chef wants to count the number of good strings which starts at letter a and ends at letter b such that starting index Si and ending index Ei of a chosen substring satisfies L <= Si < Ei <= R.
NOTE
Two substrings P1 and P2 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 P1 and string P2 respectively.
Chef is not able to accomplish this task efficiently. Can you help him ?

Input
First line of the input contains a string P denoting the chef's special string. Next line of the input contains a single integer Q denoting the number of chef's queries. Next Q lines of the input contains four space separated parameters where the first two parameters are characters denoting a and b respectively and rest two are integers denoting L and R respectively.


Output
For each chef's query, print the required answer.

Constraints

1 <= |P| <= 10^6
1 <= Q <= 10^6
1 <= L <= R <= |P|
P,a,b belongs to the set of lower case letters [c,h,e,f] and a != b.
All test files are strictly according to constraints.


Example

Input
checfcheff
5
c h 1 10
c f 1 10
e c 1 10
c f 1 5
c f 6 10

Output
4
8
2
2
2

Explanation

Q1 : good strings are ch , checfch , cfch , ch 
Q2 : good strings are checf , checfchef , checfcheff , cf , cfchef , cfcheff , chef , cheff


Warning
Large test data set, Prefer to use faster input/output methods .
ch=str(raw_input())
length=len(ch)
arr=[]
cur=0
temp=[]
for k in range(length):
     if(ch[k]=='c'):
            cur+=1
            temp.append(cur)
     else:
            temp.append(cur)
arr.append(temp)
cur=0
temp=[]
for k in range(length):
     if(ch[k]=='e'):
            cur+=1
            temp.append(cur)
     else:
            temp.append(cur)
arr.append(temp)
cur=0
temp=[]
for k in range(length):
     if(ch[k]=='f'):
            cur+=1
            temp.append(cur)
     else:
            temp.append(cur)
arr.append(temp)
cur=0
temp=[]
for k in range(length):
     if(ch[k]=='h'):
            cur+=1
            temp.append(cur)
     else:
            temp.append(cur)
arr.append(temp)
dp=[]
for i in range(4):
    dp.append([])
    for k in range(4):
        dp[i].append([0])
for i in range(4):
    for j in range(4):
        if(i==j):
            continue
        for k in range(1,length):
            if(j==0):
                if(ch[k]=='c'):
                    dp[i][j].append(dp[i][j][k-1]+arr[i][k-1])
                else:
                    dp[i][j].append(dp[i][j][k-1])
            elif(j==1):
                if(ch[k]=='e'):
                    dp[i][j].append(dp[i][j][k-1]+arr[i][k-1])
                else:
                    dp[i][j].append(dp[i][j][k-1])
            elif(j==2):
                if(ch[k]=='f'):
                    dp[i][j].append(dp[i][j][k-1]+arr[i][k-1])
                else:
                    dp[i][j].append(dp[i][j][k-1])
            elif(j==3):
                if(ch[k]=='h'):
                    dp[i][j].append(dp[i][j][k-1]+arr[i][k-1])
                else:
                    dp[i][j].append(dp[i][j][k-1])
q=int(raw_input())
for i in range(q):
    z=raw_input().split()
    ans=0
    a=z[0]
    b=z[1]
    l=int(z[2])
    r=int(z[3])
    temp2=0
    temp1=0
    if(a=='c'):
        temp1=0
    elif(a=='e'):
        temp1=1
    elif(a=='f'):
        temp1=2
    else:
        temp1=3
    if(b=='c'):
         temp2=0
    elif(b=='e'):
        temp2=1
    elif(b=='f'):
        temp2=2
    else:
        temp2=3
    if(l==1):
        ans=dp[temp1][temp2][r-1]
    else:
        ans=dp[temp1][temp2][r-1]-dp[temp1][temp2][l-2]-arr[temp1][l-2]*(arr[temp2][r-1]-arr[temp2][l-2])
    print ans