修改

题目描述

奶龙有一段由小写字母构成的字符串 $s$。

暴暴龙有一种魔法，能够任意改变字符串中的字母。但是他能改变的字母数量是有限的。

暴暴龙希望通过修改字符串让奶龙破防。

暴暴龙有 $q$ 个计划，每个计划都有一个目标字母 $c$，暴暴龙想请你告诉他，在最多改变 $m$ 个字符的情况下，他最多能够使字符串中有多少个连续相同的字母 $c$。

由于只是计划，所以 $q$ 个计划互相独立。

输入格式

第一行，一个整数 $n$，表示 $s$ 的长度；

第二行，字符串 $s$；

第三行，一个整数 $q$；

接下来 $q$ 行，每行一个整数 $m_i$ 和一个字符 $c_i$。

输出格式

共 $q$ 行，一行一个整数，输出连续的 $c$ 的数量。

样例 #1

样例输入 #1

6
koyomi
3
1 o
4 o
4 m

样例输出 #1

3
6
5

样例 #2

样例输入 #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

样例输入 #3

10
aaaaaaaaaa
2
10 b
10 z

样例输出 #3

10
10

数据范围与约定

对于 $40\%$ 的数据，$n\leq 100, q\leq 1000$；

对于 $100\%$ 的数据，$1\leq m_i\leq n \leq 1000, 1\leq q\leq 10^5$，$s,c$ 只包含小写字母。