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 50\,000)~, 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 ~1\,000~. 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