Description

So, they repeatedly write their favorite string JANJETINA on a pyramid from left to right and from top to bottom following a certain pattern.

This is what the pyramid looks like when it has only six layers:

Now they want to test you with a question: given a string $s$ and the number of layers $n$ of the pyramid, the string is written on the pyramid over and over again. Then there are $k$ queries. In the $i$-th query, you are asked how many times the character $c_i$ appears in layer $a_i$.

Input Format

The first line contains an integer $n$.

The second line contains a string $s$.

The third line contains an integer $k$.

The next $k$ lines each contain an integer $a_i$ and a character $c_i$.

Output Format

For each query, output one line with an integer representing the answer.

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

Hint

Explanation for Sample Input/Output 1

It corresponds to the example shown in the statement.

Constraints

• For $50\%$ of the testdata, it is guaranteed that $n \le 10^3$.
• For $70\%$ of the testdata, it is guaranteed that $|s| \le 10^5$.
• For $100\%$ of the testdata, it is guaranteed that $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$, and all characters in the input are uppercase letters.

Note

The total score for this problem is $100$ points.

This problem is translated from Task 3 PIRAMIDA of Croatian Open Competition in Informatics 2014/2015 Contest #1.

Translated by ChatGPT 5