The string s is called a superfix for string t if t starts with s and ends with s. For example, "abra" is a prefix for the string "abracadabra". In particular, the string t itself is its own superfix. Suprefixes play an important role in various algorithms on strings.
In this problem, it is required to solve the inverse problem of finding a suprefix, which is as follows. Given a dictionary containing n words t1, t2, …, tn and a set of m sample strings s1 , s2, …, sm. It is necessary for each sample string from the given set to find the number of words in the dictionary for which this sample string is a superfix.
It is required to write a program that, given the number n, n dictionary words t1, t2, …, tn, the given number m and m pattern strings s1, s2, …, sm will calculate for each pattern string the number of words in the dictionary for which this the pattern string is a superfix.
Input
The first line of the input file contains an integer n (1 ≤ n ≤ 200 000).
The next n lines contain the words t1, t2, …, tn, one word per line. Each word consists of lowercase letters of the Latin alphabet. The length of each word does not exceed 50. The total length of all words does not exceed 106. The dictionary does not contain empty words.
This is followed by a line containing the integer m (1 ≤ m ≤ 200,000).
The next m lines contain sample strings s1, s2, …, sm, one per line. Each sample string consists of lowercase Latin letters: The length of each sample string does not exceed 50. The total length of all sample strings does not exceed 106. No pattern string is an empty string.
Output
The output file should contain m numbers, one per line.
For each pattern string, in the order in which they are given in the input file, print the number of dictionary words for which it is a superfix.
|
Enter |
Output |
|
4
abacaba
abracadabra
aa
abra
3
a
abra
abac
|
4
2
0 |