Gene Prefix and Suffix Query

There is a gene library containing (N) strings. Each string is composed only of the characters (A), (G), (U), and (C), and each string is guaranteed to contain all four letters. Given (M) queries, each query consists of two strings (P) and (Q). For each query, determine the number of strings in the gene library that have (P) as a prefix and (Q) as a suffix.

For example, consider the string GAC. Its prefixes are G, GA, and GAC, and its suffixes are C, AC, and GAC. Thus, the string GAC has both prefix GA and suffix AC simultaneously.

inputFormat

The first line contains two integers (N) and (M).\nThe next (N) lines each contain a gene string from the library. (Each gene string is composed exclusively of the characters A, G, U, and C, and contains all four letters.)\nThe following (M) lines each contain two space-separated strings (P) and (Q), representing a query.

outputFormat

For each query, output a single integer on a separate line indicating the number of gene strings that have (P) as a prefix and (Q) as a suffix.

sample

3 3
AGUC
AUGC
GAUC
A C
GA UC
AU GC

2
1
1