Descripción

En la final regional de programación, el auditorio está lleno, las pantallas muestran el marcador en tiempo real y el público no deja de escribir mensajes en el "Muro de fans", una enorme pantalla donde aparecen todos los textos enviados.

El comité organizador quiere saber qué tan "queridas" son ciertas letras dentro de todos esos mensajes.

Para ello, guardan todos los mensajes concatenados en una sola cadena \(S\) de longitud \(N\), formada únicamente por letras minúsculas ('a'–'z').

Después, reciben \(Q\) consultas del tipo:

"¿Cuántas veces aparece la letra \(c\) en toda la cadena \(S\)?"

Tu misión, como parte del equipo de jueces, es responder rápidamente a cada una de estas consultas, antes de que el público envíe aún más mensajes y la próxima ronda de problemas comience.

Entrada

En la primera línea, un entero \(N\) \((1 \leq N \leq 10^6)\) — la longitud de la cadena.

En la segunda línea, una cadena \(S\) de longitud \(N\), formada únicamente por letras minúsculas ('a'–'z').

En la tercera línea, un entero \(Q\) \((1 \leq Q \leq 10^6)\) — el número de consultas.

En cada una de las siguientes \(Q\) líneas, aparece un solo carácter \(c\), una letra minúscula ('a'–'z'), para la cual se desea saber cuántas veces aparece en \(S\).

Salida

Imprimir \(Q\) líneas.

En la \(i\)-ésima línea, imprimir un solo número entero: el número de veces que la letra de la \(i\)-ésima consulta aparece en la cadena \(S\).

Ejemplos

Entrada

7
icpcmex
3
c
x
z

Salida

2
1
0

Entrada

10
aaaaabbbbb
2 
a
b

Salida

5
5