Fie un şir de caractere $S$. Numim bâlbâială de ordin $k$ a lui $S$ şirul obţinut prin multiplicarea fiecărui caracter al lui $S$ de exact $k$ ori. Spre exemplu, bâlbâiala de ordin $2$ a şirului "andrei" este şirul "aannddrreeii", iar bâlbâiala de ordin $3$ a şirului "ana" este şirul "aaannnaaa".

Fie un şir de caractere $A$ şi $Q$ şiruri de caractere B{~1~}, B{~2~}, .. B{~Q~}. Pentru fiecare şir $B$, dorim să aflăm bâlbâiala de ordin maxim a respectivului şir care apare ca subşir în şirul $A$. Spre exemplu, pentru $A = "onomatopee"$ şi $B = "oe"$, ordinul maxim al bâlbâielii este egal cu $2$.

Fie un şir de caractere $A$ şi $Q$ şiruri de caractere B{~1~}, B{~2~}, .. B{~Q~}. Pentru fiecare şir $B$, dorim să aflăm bâlbâiala de ordin maxim a respectivului şir care apare ca subşir în şirul $A$. Spre exemplu, pentru $A = "onomatopee"$ şi $B = "oe"$, ordinul maxim al bâlbâielii este egal cu $2$, iar pentru $B' = "z"$, ordinul maxim al bâlbâielii este egal cu $0$.

h2. Date de intrare

Fişierul de intrare $balbaiala.in$

Fişierul de intrare $balbaiala.in$ contine pe prima linie numerele naturale $N$ (marimea sirului $A$) si $Q$ (numarul de siruri $B{~i~}$), pe a doua linie sirul $A$ de caractere, iar pe urmatoarele $Q$ linii sirurile $B{~i~}$.

h2. Date de ieşire

În fişierul de ieşire $balbaiala.out$ ...

În fişierul de ieşire $balbaiala.out$ se vor afla $Q$ linii, pe a $i$-a dintre ele fiind un numar natural reprezentand ordinul maxim al bâlbâielii sirului $B{~i~}$ care sa apara ca subsir in sirul $A$.

h2. Restricţii