#3413. 匹配

题目描述

.jpg)

输入格式

第一行包含一个整数n(≤100000)。

第二行是长度为n的由0到9组成的字符串。

第三行是一个整数m。

接下来m≤5*10行，第i行是一个由0到9组成的字符串s，保证单行字符串长度小于等于10^5，所有字符串长度和小于等于3*10^6

输出格式

输出m行，第i行表示第si和S匹配所比较的次数。

样例

样例输入

7  

1090901  

4  

87650  

0901  

109  

090

样例输出

7  

10  

3  

4

数据范围与提示