Repeating Tower Query

Given a string s and an integer n representing the number of levels in a tower, you fill the tower by writing the string repeatedly according to the following rule:

• The tower has n levels.
• The i-th level contains exactly i characters.
• You write the string s repeatedly in reading order (from left to right and from top to bottom). When the end of the string is reached, you start over from the beginning.

After the tower is filled, there will be k queries. In the i-th query, you are given a level number ai and a character ci. Your task is to output the number of times the character ci appears in the ai-th level of the tower.

Note: All formulas are expressed in LaTeX. In particular, the starting index (0-based) for a level i is given by \(\frac{(i-1) \cdot i}{2}\).

inputFormat

The first line contains a string s and an integer n separated by a space.

The second line contains an integer k, the number of queries.

Each of the following k lines contains an integer ai and a character ci separated by a space, representing a query asking for the number of occurrences of character ci in the ai-th level of the tower.

outputFormat

For each query, output a single integer on a new line, indicating the number of occurrences of the given character in the specified level.

sample

JANJETINA 6
3
1 J
6 A
6 N

1
2
2