a11y

Have you ever heard of the word a11y? It is an abbreviation of accessibility, where there are 11 characters between the a and the y. Similar abbreviations include k8s (Kubernetes) and i18n (internationalization).

You are given a string $A$ of length $N$. Given queries, each an abbreviation made of a letter, a number, and a letter, print how many substrings of $A$ match each abbreviation. When counting, two substrings with the same content but different positions in $A$ are counted as different.

A substring of a string is a string obtained by removing zero or more characters from either end. For example, the substrings of abc are a, b, c, ab, bc, and abc, for a total of $6$.

The first line contains the string $A$ of length $N$, which consists only of lowercase English letters. ($1\le N\le 100\,000$)

The next line contains the number of queries $Q$. ($1\le Q\le 100\,000$)

Each of the next $Q$ lines contains an abbreviation with no spaces, in the form letter, number, letter. Both letters are lowercase English letters, and the middle number is between $1$ and $N-2$, inclusive.

Print the answer to each query on its own line, in the order the queries are given.