PIRAMIDA

문제

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 in the back garden and wrote their favorite word on it, repeating it from line to line and changing direction, as shown in the picture.

     J
    N A
   J E T
  J A N I
 A N J E T
N A J A N I

Pyramid of the height 6 marked with the word "JANJETINA"

Tomislav has now chosen K lines of the pyramid, marked with ai, and has chosen a letter ci for each line. Then he asked Zoran K tricky questions: "How many times does the lettet ci 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¹⁸).

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⁶.

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 a_i, c_i (1 ≤ a_i ≤ N, c_i uppercase letter of the English alphabet) which represent Tomislav's questions.

출력

Output K lines. The ith line of output must contain a single integer - the number of appearances of letter c_i in the row a_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