Alan y Ada no tienen nada importante que hacer pero hoy se les ocurrió construir una pirámide de letras con una altura N. Luego escriben su palabra favorita línea por línea comenzando desde el nivel N y cambiando la dirección en cada línea como se muestra en el ejemplo a continuación: Pirámide de altura 6 y construida con la palabra ” JANJETINA”:

Ada toma ~K~ lineas de la piramide denotadas como ~a_i~ y elige una letra ~c_i~ por cada línea y luego le pregunta a Alan cuantas veces aparece la letra ~c_i~ en la línea ~a_i~.Tu tarea es hacer un programa que ayude a Alan a respoder las preguntas.

Entrada:

La primera línea contiene un entero ~N (1 \leq N \leq 10^{18})~. La segunda línea contiene una cadena ~S~ (a lo sumo tendrá ~10^6~ letras mayúsculas del alfabeto ingles) que es la palabra favorita. La tercera línea contiene un entero ~K (1 \leq K \leq 50000)~ el numero de preguntas de Ada. Las siguientes ~K~ líneas contendrán el enteros ~a_i (1 \leq a_i \leq N)~ y el carácter ~c_i~.

Salida:

Imprime K líneas. La ~i^{th}~ línea debe contener un solo entero el número de veces que se repite la letra ~c_i~ en la línea ~a_i~.

Ejemplo de Entrada

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

Ejemplo de Salida:

1
0
2
1
1