Dada una cadena y un conjunto de patrones, determine para cada patrón la cantidad de posiciones en las que aparece en la cadena.
La primera línea contiene una cadena de longitud n~(1 \le n \le 10^5).
La segunda línea contiene un entero k~(1 \le k \le 5 \cdot 10^5) — la cantidad de patrones. Cada una de las siguientes líneas contiene un patrón. La longitud total de todos los patrones no supera 5 \cdot 10^5.
La cadena y los patrones consisten en letras minúsculas del alfabeto latino '' - ''.
Para cada patrón, imprima en una línea separada la cantidad de sus apariciones en la cadena.
Ejemplo 1