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 $a_i$, and has chosen a letter $c_i$ for each line. Then he asked Zoran $K$ tricky questions: "How many times does the letter $c_i$ appear in the row $a_i$?"

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

Input

The first line of input contains the integer $N$ $(1\le N\le {10}^{18})$.
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\le K\le 50000)$, the number of lines Tomislav has chosen.
Each of the following $K$ lines contains the pair $a_i$, $c_i$ ($1\le a_i\le N$, $c_i$ uppercase letter of the English alphabet) which represent Tomislav's questions.

Output

Output $K$ lines. The $i^{th}$ line of output must contain a single integer – the number of appearances of letter $c_i$ in the row $a_i$.

Scoring

In test cases worth 50% of total points, $N$ will not exceed $1000$. In test cases worth 70% of total points, length of the string will not exceed ${10}^5$.

Sample Input 1

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

Sample Output 1

1
0
2
1
1

Explanation for Sample 1

See the pyramid in the task statement.

Sample Input 2

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

Sample Output 2

1
2
3
4
0

Sample Input 3

3
AB
3
2 A
2 B
3 B

Sample Output 3

1
1
2