Matching Bracket Pairs Query

Given a string S that consists of lowercase letters and parentheses, where the parentheses are guaranteed to be properly matched, and Q queries, answer the following:

Each query provides a lowercase letter c and an integer x. For each query, count how many matching parenthesis pairs in S contain at least x occurrences of the letter c between them.

Note: For a matching pair, consider only the letters between the opening and closing parentheses (i.e. if the pair starts at index i and ends at index j, consider the substring S[i+1...j-1]).

inputFormat

The first line contains the string S. The second line contains an integer Q, the number of queries. Each of the following Q lines contains a lowercase letter and an integer x separated by a space.

outputFormat

For each query, output a single integer representing the number of matching parenthesis pairs that have at least x occurrences of the specified letter between them.

sample

a(bc)de(fga)
2
b 1
a 1

1
1