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