题目描述

驼鹿 Valera 很喜欢玩一种叫做“Contact”的文字游戏。不过传统玩法至少需要三个人，于是他设计了一个双人版本。

第一名玩家先秘密选择一个非空单词 $S$，第二名玩家需要猜出它。开始时，第一名玩家只公布 $S$ 的第一个字母。

第二名玩家不断猜测以当前已公布前缀开头的单词，第一名玩家告诉他猜测是否正确。第二名玩家不能重复猜同一个单词。

预先给定一个整数 $K$。如果第二名玩家连续猜了 $K$ 个单词仍未猜中，则第一名玩家再公布 $S$ 的下一个字母。之后，第二名玩家只能猜以更长的已知前缀开头、且此前从未猜过的单词。

每当又进行了 $K$ 次失败猜测，就继续公布一个字母。

如果 $S$ 的全部字母都已经被公布，而第二名玩家又猜了 $K$ 个以 $S$ 为前缀的单词，却仍没有猜中 $S$ 本身，那么第一名玩家直接告诉他：当前已公开的字母本身就是答案，游戏结束。

一次成功猜测也计入第二名玩家总共说出的单词数量。

现在给定第二名玩家掌握的完整词典。Valera 总会从这个词典中选取谜底，因此第二名玩家一定认识谜底。

对 $Q$ 个询问，每个询问给出一个词典中的目标单词以及参数 $K$。假设第二名玩家采取策略，使自己在游戏结束前能够说出尽可能多的单词，求这个最大数量。

输入格式

第一行包含一个正整数 $N$，表示词典中的单词数量。

接下来 $N$ 行，每行一个由小写英文字母组成的非空单词。

所有单词长度之和不超过

注意：词典中允许出现拼写完全相同的单词。它们可以被理解为读音、重音等方面不同，因此在游戏过程中仍被视为不同单词。

接下来一行包含整数 $Q$：

接下来 $Q$ 行，每行包含两个整数 $w,k$：

• $w$ 表示谜底为输入中的第 $w$ 个单词；
• $k$ 表示本次游戏中的参数 $K$。

输出格式

对于每个询问，输出一行一个整数：第二名玩家在游戏结束之前最多可以说出的单词数量。

样例 1

6
asassin
assistant
astronaut
abrakadabra
abbey
automaton
9
1 1
1 2
1 3
4 1
4 2
4 3
6 1
6 2
6 3

3
5
6
3
4
5
2
3
4

样例 2

3
aa
ab
ab
6
1 1
2 1
1 2
3 2
2 2
3 1

2
2
3
3
3
2

样例 3

7
pit
pitbul
piter
pitstop
pitlane
petroleum
pistol
6
1 2
1 3
6 4
7 2
7 3
5 1

6
7
5
5
7
4