如果两个单词在不区分大小写的情况下相等，但在区分大小写的情况下，它们在不超过 $K$ 个位置上不同，则认为这两个单词是相似的。

给定一个包含 $W$ 个单词的词典以及 $Q$ 个查询单词。对于每个查询单词，输出一个整数：词典中与之相似的单词数量。

输入格式

第一行包含一个整数 $K$ — 单词在大小写上可以不同的最大位置数（$0 \le K \le 5$）。

第二行包含一个整数 $W$ — 词典中的单词数量（$1 \le W \le 1\,000$）。

接下来的 $W$ 行包含词典，每行一个单词。每行由大小写拉丁字母组成。所有单词均非空，且长度不超过 $2\,000$ 个字符。

下一行包含一个整数 $Q$ — 查询的数量（$1 \le Q \le 1\,000$）。

接下来的 $Q$ 行包含查询，每行一个单词。与词典中的单词相同，每个查询由大小写拉丁字母组成，所有查询均非空，且每个查询的长度不超过 $2\,000$ 个字符。

输出格式

对于输入的每个 $Q$ 查询，输出一个整数：词典中相似单词的数量。对查询的回答必须按照输入中查询出现的顺序依次输出。

样例

输入样例 1

2
5
theword
TheWord
THEWORD
thewordandsomeletters
theword
4
theword
The
theword
TheWordAndSomeLetters

输出样例 1

3
0
3
0