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

第二行包含 $n$ 个小写英文字母组成的字符串 s1s2…sns_{1} s_2 \ldots s_ns​1​​s​2​​…s​n​​ —— 给定的初始字符串。

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

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

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

样例输入 1

6
koyomi
3
1 o
4 o
4 m

样例输出 1

3
6
5

样例解释 1

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

• 在第一个询问中，最多可以更改 $s$ 一个位置上的字符，将 $\text{y}$ 所处的位置改为 $\text{o}$ 得到 $s^{\prime }=\text{kooomi}$，权值为 $3$；
• 在第二个询问中，最多可以更改 $s$ 四个位置上的字符，$s^{\prime }=\text{oooooo}$ 的权值为 $6$；
• 在第三个询问中，最多可以更改 $s$ 四个位置上的字符，$s^{\prime }=\text{mmmmmi}$ 和 $s^{\prime }=\text{kmmmmm}$ 的权值均为 $5$。

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

$1\le n\le 1500$
$1\le q\le 200000$
1≤mi≤n1 \leq m_i \leq n1≤m​i​​≤n，cic_ic​i​​ 为小写英文字母