Description

Format

Input

第一行包含一个整数n(≤100000)。 第二行是长度为n的由0到9组成的字符串。 第三行是一个整数m。接下来m≤5·10行，第i行是一个由0到9组成的字符串s，保证单行字符串长度小于等于10^5，所有字符串长度和小于等于3·10^6

Output

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

Samples

7
1090901
4
87650
0901
109
090

7
10
3
4