E. 恋爱循环

字符串 对于字符 的权值，定义为 中仅由 组成的最长连续子串的长度。例如，对于 ，其由字符 组成的最长连续子串为 ，因此它对于字符 的权值为 。

给定由小写字母组成的字符串 以及 个询问。每个询问形如 ，表示「求出在 中至多更改 个位置的字符后所得的字符串 对于字符 的最大权值」。

输入的第一行包含一个正整数 —— 字符串 的长度。

第二行包含 个小写英文字母组成的字符串 —— 给定的初始字符串。

第三行包含一个正整数 —— 询问的数目。

接下来 行，每行包含一个正整数 —— 至多在 中更改的字符数目，和以一个空格分隔的小写字母 —— 计算权值时使用的字符。

输出 行：对于每个询问输出一行，包含一个整数 —— 进行更改后所得字符串 的最大权值。

样例输入 1

6
koyomi
3
1 o
4 o
4 m

样例输出 1

3
6
5

样例解释 1

在样例 1 中，有三个询问：

• 在第一个询问中，最多可以更改 一个位置上的字符，将 所处的位置改为 得到 ，权值为 ；
• 在第二个询问中，最多可以更改 四个位置上的字符， 的权值为 ；
• 在第三个询问中，最多可以更改 四个位置上的字符， 和 的权值均为 。

样例输入 2

15
yamatonadeshiko
10
1 a
2 a
3 a
4 a
5 a
1 b
2 b
3 b
4 b
5 b

样例输出 2

3
4
5
7
8
1
2
3
4
5

样例输入 3

10
aaaaaaaaaa
2
10 b
10 z

样例输出 3

10
10

， 为小写英文字母