Ssari and Bird's Pyramid

Ssari and Bird had nothing at all to do, so they built a pyramid of height $N$ in the back yard and decided to write their favorite word on it. Row $i$ from the top has $i$ cells.

The word goes in one letter per cell, in a zigzag. Row 1 fills from left to right, row 2 from right to left, row 3 from left to right again, and so on. Once the word is written out, it starts over from its first letter.

For $N = 6$ and the word JANJETINA the pyramid comes out like this.

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

Bird picks a row number $a_i$ and an uppercase letter $c_i$, then asks "how many times does $c_i$ appear in row $a_i$?". Answer Bird's $K$ questions and help Ssari out.

The first line contains the height of the pyramid, $N$ ($1 \le N \le 10^{18}$).

The second line contains a word made only of uppercase letters. The word is at most $10^6$ letters long.

The third line contains the number of rows Bird picked, $K$ ($1 \le K \le 50000$).

Each of the next $K$ lines contains $a_i$ and $c_i$ separated by a space ($1 \le a_i \le N$, and $c_i$ is an uppercase letter).

Print $K$ lines. Line $i$ holds the number of times $c_i$ appears in row $a_i$ of the pyramid.