题目描述

给你一个由小写字母构成的字符串 $s$ 和 $q$ 次询问，每个询问给出数字 $m$ 和小写字母 $c$。你可以任意地修改字符串中的 $m$ 个字符，求最多能够使字符串中含有多少个连续相同的字母 $c$。

输入格式

第一行一个整数 $n$，$1⩽n⩽1500$。

第二行是一个长度为 $n$ 的字符串 $s$。

第三行一个整数 $q$，$1⩽q⩽2×10^5$。

接下来 $q$ 行，每行一个整数 $m_i$ 和一个小写字母 $c_i$，$1⩽m_i⩽n$。

输出格式

对于每次询问，在一行中输出一个整数表示答案。

6
koyomi
3
1 o
4 o
4 m

3
6
5

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

3
4
5
7
8
1
2
3
4
5

10
aaaaaaaaaa
2
10 b
10 z

10
10