Megint írógép

Péternek van egy régi írógépe, melyen a betűk (jelek) egymás mellett vannak, némelyik többször is előfordulhat rajta. A gépelés megkezdése előtt egy fejet az írógép végein található helyekre kell illeszteni (ezek aláhúzással (_) vannak jelölve az írógép leírásában). A fejet jobbra-balra mozgathatjuk a betűk felett. Van egy gomb is rajta amit ha megnyomunk, akkor a gép memórájába kerül a betű ami felett állunk. Egy szomszédos billentyű eléréséhez 1 másodpercre van szükség, a gomb megnyomásához szükséges idő elhanyagolható. Számoljuk ki a soronként adott szövegekre, hogy minimálisan hány időegységre van szükség a gép memórájába vitelükhöz.

Bemenet specifikáció

Az első sor az írógépet tartalmazza: egy aláhúzás (_) jelekkel határolt $K$ hosszú sztring (tehát a teljes hossz $K+2$). A következő sorban a szövegek $C$ száma van, majd ennyi sor következik mindegyikben egy-egy kettőskereszttel (#) határolt legfeljebb $L$ hosszú sztring. A # nem része a szövegnek, csak a szövegek végein esetlegesen előforduló üreshelyek miatt szerepel. Az írógépen és a szövegsorokban az angol abc kisbetűi és üreshely jelek fordulnak csak elő.

Kimenet specifikáció

$C$ sor a kiszámolandó mennyiségekkel. Ha nem lehetséges az adott szöveget bevinni a gép memórájába, akkor írjunk $-1$-et.

Korlátok

$1\le K \le 500$
$0\le L \le 300$
$0\le C \le 200$

1. példa bemenet

1. _abc _
2. 7
3. #abc#
4. #cba#
5. #abcba#
6. ##
7. #abababa#
8. #ab ab#
9. #abcd ab #

1. példa kimenet

1. 3
2. 4
3. 5
4. 0
5. 7
6. 8
7. -1