题目描述

金字塔有N层，从上往下数，第1层有1个格子，第2层有2个格子。。。最层下的层有N个格子。奶牛Bessie很喜欢字符串，于是它把字符串S的每个字符分别写到金字塔上，次序是这样的：从金字塔的上层往下层写，每个格子只能写一个字符，每一层都是从左往右写，或者从右往左写，而且相邻两层的方向要相反，更具体就是：从上往下数，奇数层的方向是从左往右写，偶数层的方向是从右往左写。如果字符串S的所有字符都写完了，而此时金字塔还有空的格子，怎么办？奶牛Bessie会重复把S再接着往下写，一直到把金字塔所有格子都写满为止。例如：Bessie要把字符串“JANJETINA”写满高度为6层的金字塔，那么是这样的：

现在有K个问题你需要回答，每个问题给出两个参数：ai、ci, 表示的意义是：金子塔的第ai层有多少个字符ci?

输入格式

第一行，一个整数N。

第二行，一个字符串S。字符串S全部有大写字母构成，长度不超过10^6。

第三行，一个整数K。表示有K个问题。1 <=K<=50000。

接下来有K行，每行两个参数：ai和ci。 1 <= ai <= N, ci是一个大写字母。

输出格式

共K行，每行一个整数，第i行对应第i个问题的答案。

样例输入/输出

6
JANJETINA
5
1 J
1 A
6 N
6 I
5 E

1
0
2
1
1

5
A
5
1 A
2 A
3 A
4 A
5 B

1
2
3
4
0

数据规模与提示

1、对于50%的数据， 1<=N <= 10^3。

2、对于70%的数据， 1<=N <= 10^5。

3、对于100%的数据，1<=N <= 10^18。