레이팅 미적용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.
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\).
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 \(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\).
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