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