题目描述

定义两个字符串的公共前缀为这两个字符串从开头开始的公共子串。比如，字符串 identity 和字符串 idealistic 的公共前缀为 ide。

有一个数据库包含了 $N$ 个字符串。

在这个数据库中查询字符串 $W$ 使用的算法很原始，它将 $W$ 与数据库中的字符串一一比较。两个字符串的字符也一一比对，直到找到一个不匹配的字符或者其中一个字符串的结尾，然后进行最后一次比较确定两个字符串长度是否相等。当在数据库中找到 $W$ 时，算法结束。

分析这个算法，我们发现，在数据库中找到 $W$ 所用的步骤数等于与 $W$ 进行比较的字符串数量，加上 $W$ 与所有进行比较的字符串的公共前缀之和。

共有 $Q$ 个需查询的字符串。

写出一个程序，计算对于每一个字符串，程序需要多少步才能在数据库中找到这个词。

请留意本题非同寻常的内存限制。

输入格式

第一行，一个整数 $N$，表示数据库中字符串的个数。

接下来 $N$ 行，每行一个数据库中的字符串，这些字符串按照算法的查询顺序给出，互不相同。

接下来一行，一个整数 $Q$，表示需查询的字符串数。

接下来 $Q$ 行，每行一个需查询的字符串。

输出格式

对于每个查询字符串，输出一行，一个整数，表示程序在数据库中找到这个词所需的步数。

5
hobotnica
robot
hobi
hobit
robi
4
robi
hobi
hobit
rakija 

12
10
16
7 

8
majmunica
majmun
majka
malina
malinska
malo
maleni
malesnica
3
krampus
malnar
majmun 

8
29
14

提示

对于 $100\%$ 的数据，$1\le N,Q\le 3\times 10^4$，所有字符串长度 $<30$，且只包含小写字母。

样例 2 解释：

对于样例 2，搜索字符串 krampus 所用的步数为 $8$，我们只需要将数据库里每一个字符串的第一个字符与此字符串比较即可。

搜索字符串 malnar 时，前三个字符串每个字符串需要比较三次，剩下五个字符串每个字符串则需要比较四次，所以总共需要 $29$ 次比较。

为了找到 majmun 字符串，我们总共需要 $14$ 次比较。对于第一个单词，我们进行了六次成功的比较，但最后一次比较确定了字符串 majmunica 比 majmun 长。对于第二个字符串，我们也进行了六次成功的比较，在最后一次比较中我们发现两个字符串长度相等，算法结束。

本题分值按照原比赛设置，满分 $90$ 分。