背景

Zoran 和 Tomislav 今天很无聊。

题目描述

于是，他们把他们喜欢的字符串 JANJETINA 按照一定规律在一个塔上从左到右从上到下写了一遍又一遍。

这是塔只有六层的情况：

现在他们想考你一个问题：给定字符串 $s$ 与塔的层数 $n$，将这个字符串在塔上写一遍又一遍，接下来会有 $k$ 个问题，第 $i$ 次问你字符 $c_i$ 在第 $a_i$ 层出现了几次。

输入格式

第一行一个整数 $n$。

第二行一个字符串 $s$。

第三行一个整数 $k$。

接下来 $k$ 行，第 $i$ 行为一个整数 $a_i$ 和一个字符 $c_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

3
AB
3
2 A
2 B
3 B

1
1
2

提示

样例输入输出 1 解释

为题目中的例子。

数据规模与约定

• 对于 $50\%$ 的数据，保证 $n\le 10^3$。
• 对于 $70\%$ 的数据，保证 $|s|\le 10^5$。
• 对于 $100\%$ 的数据，保证 $1\le n \le 10^{18}$，$1\le |s|\le 10^6$，$1\le k\le 5\times 10^4$，$1\le a_i\le n$，输入中涉及的字符均为大写字母。

说明

本题总分 $100$ 分。

本题译自 Croatian Open Competition in Informatics 2014/2015 Contest #1 T3 PIRAMIDA。