CF814C.An impassioned circulation of affection

Nadeko's birthday is approaching! As she decorated the room for the party, a long garland of Dianthus-shaped paper pieces was placed on a prominent part of the wall. Brother Koyomi will like it!

Still unsatisfied with the garland, Nadeko decided to polish it again. The garland has n pieces numbered from 1 to n from left to right, and the i-th piece has a colour s__i, denoted by a lowercase English letter. Nadeko will repaint at most m of the pieces to give each of them an arbitrary new colour (still denoted by a lowercase English letter). After this work, she finds out all subsegments of the garland containing pieces of only colour c — Brother Koyomi's favourite one, and takes the length of the longest among them to be the Koyomity of the garland.

For instance, let's say the garland is represented by "kooomo", and Brother Koyomi's favourite colour is "o". Among all subsegments containing pieces of "o" only, "ooo" is the longest, with a length of 3. Thus the Koyomity of this garland equals 3.

But problem arises as Nadeko is unsure about Brother Koyomi's favourite colour, and has swaying ideas on the amount of work to do. She has q plans on this, each of which can be expressed as a pair of an integer m__i and a lowercase letter c__i, meanings of which are explained above. You are to find out the maximum Koyomity achievable after repainting the garland according to each plan.

奈绪子的生日快到了！她在为派对装饰房间时，将一串形似石竹花的纸片花环挂在了墙面一个十分醒目的位置。小哥光洋一定会喜欢的！

不过，奈绪子对这串花环仍不甚满意，决定再加以修饰。该花环由 $n$ 个纸片组成，从左至右依次编号为 $1$ 到 $n$；其中第 $i$ 个纸片的颜色为 $s_i$，用一个小写英文字母表示。奈绪子最多可重新粉刷其中 $m$ 个纸片，将它们涂成任意新颜色（仍用小写英文字母表示）。完成粉刷后，她找出花环中所有仅由颜色 $c$（即小哥光洋最钟爱的颜色）构成的连续子段，并将其中最长子段的长度定义为该花环的“光洋度”（Koyomity）。

例如，假设花环表示为字符串 "kooomo"，而小哥光洋最钟爱的颜色为 "o"。在所有仅含 "o" 的连续子段中，"ooo" 是最长的，其长度为 $3$。因此该花环的光洋度为 $3$。

然而，问题出现了：奈绪子并不确定小哥光洋最喜欢的颜色究竟是哪一个，而且她对要投入多少工作量也摇摆不定。她为此制定了 $q$ 个计划，每个计划可用一个整数 $m_i$ 和一个小写字母 $c_i$ 表示，其含义如上所述。你需要针对每个计划，计算出在按该计划粉刷花环后所能达到的最大光洋度。

The first line of input contains a positive integer n (1 ≤ n ≤ 1 500) — the length of the garland.

The second line contains n lowercase English letters _s_1_s_2... s__n as a string — the initial colours of paper pieces on the garland.

The third line contains a positive integer q (1 ≤ q ≤ 200 000) — the number of plans Nadeko has.

The next q lines describe one plan each: the i-th among them contains an integer m__i (1 ≤ m__i ≤ n) — the maximum amount of pieces to repaint, followed by a space, then by a lowercase English letter c__i — Koyomi's possible favourite colour.

输入的第一行包含一个正整数 $n$（$1 \leq n \leq 1 500$）——花环的长度。

第二行包含一个由 $n$ 个小写英文字母组成的字符串 $s_1s_2...s_n$ —— 花环上纸片的初始颜色。

第三行包含一个正整数 $q$（$1 \leq q \leq 200 000$）—— 奈濑子拥有的计划数量。

接下来的 $q$ 行每行描述一个计划：其中第 $i$ 行包含一个整数 $m_i$（$1 \leq m_i \leq n$）—— 最多可重绘的纸片数量，后跟一个空格，再跟一个小写英文字母 $c_i$ —— 小夜美的可能最喜欢的颜色。

Output q lines: for each work plan, output one line containing an integer — the largest Koyomity achievable after repainting the garland according to it.

输出 q 行：对于每个工作计划，输出一行，包含一个整数——即按照该计划重新粉刷花环后所能达到的最大“Koyomity”值。

In the first sample, there are three plans:

• In the first plan, at most 1 piece can be repainted. Repainting the "y" piece to become "o" results in "kooomi", whose Koyomity of 3 is the best achievable;
• In the second plan, at most 4 pieces can be repainted, and "oooooo" results in a Koyomity of 6;
• In the third plan, at most 4 pieces can be repainted, and "mmmmmi" and "kmmmmm" both result in a Koyomity of 5.

在第一个样例中，存在三种方案：

• 在第一种方案中，最多可重绘 1 个字符。将字符 "y" 重绘为 "o"，得到字符串 "kooomi"，其 Koyomity 值为 3，是可达到的最优值；
• 在第二种方案中，最多可重绘 4 个字符，得到字符串 "oooooo"，其 Koyomity 值为 6；
• 在第三种方案中，最多可重绘 4 个字符，字符串 "mmmmmi" 和 "kmmmmm" 的 Koyomity 值均为 5。