Given two strings, S1 and S2, we can define an edit distance as the minimum number of operations required to change S1 to S2.
The operations might be one of the following:
- delete a character
- insert a character
- substitute a character for another character
For example, for the words "beer" and "bread" the edit distance would be 3. We need to perform three operations to transform "beer" into "bread":
- substitute 'e' at the second position for 'r'
- substitute 'r' at fourth position for 'a'
- insert 'd' at the end of the word
You are given a dictionary and a list of queries. Each query contains a misspelled word and an estimated maximum number of typos in it. Your task is, for each query, to find the number of corrected word candidates from the dictionary that are not further (in terms of edit distance) from the misspelled word than the corresponding number of typos.
The first line contains an integer (1 <= n <= 100000) defining the number of words in the dictionary.
The next n lines contain non-empty words of the dictionary. The words are composed of latin alphabet characters. The length of each word is up to 30 chars.
The next line is an integer representing the number of queries (1 <= m <= 1000)
The next m lines contain the misspelled words (non-empty strings) followed by their maximum edit distances e (0 <= e <= 3) for this word.
Limits for test: memory - 512M, time - 4 seconds
Print the answer to each query on a single line.
Example input
4
funny
Hellow
Helo
Helro
3
Hello 1
fun 2
fun 1
Example output
3
1
0