문제

Zoran and Tomislav don't really have anything important to do, so they spend their days doing various activities. Today, they built a pyramid of the height N on the back garden and wrote their favorite word on it, repeating it from line to line and changing direction, as shown in the picture.

Tomislav has now chosen K lines of the pyramid, marked with ai, and has chosen a letter ei for each line. Then he asked Zoran K tricky questions: "How many times does the letter ei appear in the row ai?"

You are Zoran's counselor. Write a programme that will, for the given pyramid height and their favorite word, answer Tomislav's questions.

입력

The first line of input contains the integer N (1 ≤ N ≤ 10^6), the second line of input contains a word that consists of only uppercase letters of the English alphabet. The word's length will not exceed 10^6.

The third line of input contains the integer K (1 ≤ K ≤ 50 000), the number of lines Tomislav has chosen.

Each of the following K lines contains the pair ai, ei (1 ≤ ai ≤ N, ei uppercase letter of the English alphabet) which represent Tomislav's questions.

출력

Output K lines, the i-th line of output must contain a single number — the number of appearances of letter ei in the row ai.

예제 입력 1

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

예제 출력 1

1
0
2
1
1

예제 입력 2

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

예제 출력 2

1
2
3
4
0

예제 입력 3

3
AB
3
2 A
2 B
3 B

예제 출력 3

1
1
2