Google Suggest is a typical feature of the Google search box. It guesses what you're typing and offers suggestions in real time(Fig 1). Sometimes, we may mistype the keyword. For example, when we want to find the information of "mcgrady"(a famouse NBA star), we mistyped it to "macgrady"(Fig 2). The clever Google can still give you the right suggestions. It is amazing, isn't it?

Fig 1:Google Suggest	Fig 2:Fuzzy Google Suggest

In this problem, your job is to implement a similar system. You will be given a data set including a large amount of English words. Your system should provide the search service. For each input query word, find the prefix-fuzzy-match words from the data set and ouput the number of those words. In the following, I will explain you the prefix fuzzy match. When we say the two words are fuzzy-match(without "prefix"), we mean that they look similar and their Edit Distance meets a given threshold(If you have no idea of the Edit Distance, please refer to the Hints below). When we say the word A is prefix-fuzzy-match(with "prefix") to the word B, we mean that there exists a prefix p of word B , and the Edit Distance between p and B meets a given threshold. For Example, the data set contains four English words: "content"、"common"、"onganize"、"case". The input query contains a word "con" and a Edit Distance threshold 1. "con" is prefix-fuzzy-match to the words "content"、"common"、"onganize", but "case" doesn't meet the condition, because the minimun Edit Distance between all of its prefixes and "con" is 2 which is larger than the given threshold 1.