Annettuna on merkkijono sekä joukko haettavia merkkijonoja. Tehtäväsi on ilmoittaa jokaisesta haettavasta merkkijonosta sen esiintymien määrä.

Syöte

Syötteen ensimmäisellä rivillä on merkkijono, jossa on $n$ merkkiä.

Seuraavalla rivillä on kokonaisluku $k$: haettavien merkkijonojen määrä. Tämän jälkeen on $k$ riviä, jotka kuvaavat merkkijonot.

Kaikki merkkijonot muodostuvat merkeistä a...z.

Tuloste

Ilmoita jokaisesta haettavasta merkkijonosta sen esiintymien määrä.

Rajat

• $1 \le n \le 10^5$
• $1 \le k \le 5 \cdot 10^5$
• haettavien merkkijonojen yhteispituus on enintään $5 \cdot 10^5$

Esimerkki

Syöte:

aybabtu
3
bab
abc
a

Tuloste:

1
0
2