You are given a string \(S\) of length \(N\) consisting of lowercase english alphabets and you are required to process \(Q\) queries. Each query is of the form \((a_i,b_i)\), where \(a_i\) and \(b_i\) are characters from the english lowercase alphabet. You should print the number of substrings of \(S\), whose first character is \(a_i\) and last character is \(b_i\)

A substring is obtained by removing a prefix and a suffix of the string. Two substrings \(s_{i1}...s_{j1}\) and
\(s_{i2}...s_{j2}\) are different if the ordered pair \((i_1,j_1)\) is different from \((i_2,j_2)\).

Input Format

The first line contains the string \(S\).
The second line contains the integer \(Q\), the number of queries.
Each of the next \(Q\) lines contains two characters \(a_i\) and \(b_i\), separated by a space.

Output Format

For each query, output the number of substrings of \(S\), whose first character is \(a_i\) and last character is \(b_i\).

Constraints

\(1 \leq N \leq 10^5\)
\(1 \leq Q \leq 10^5\)
The characters in \(S\) are all lowercase English letters