Pentru a adera la cultul shaman al vechilor vindecători,  pretendenţii trebuie să treacă testul cu mai multe probe pregătit de Marea Shamaniţă Bulbuka. Pretendentului **i** se arată trei tipuri de cristale cu o proprietate cu totul şi cu totul nemaivăzută: dacă oricare două cristale de tipuri diferite sunt combinate, acestea se vor transforma ireversibil într-un singur cristal de tipul al treilea (de exemplu, având cristale de tipurile **x y z**, dacă sunt alăturate **x** şi **z**, se transformă în **y**). Testul constă din **P** probe pe care trebuie să le parcurgă în ordine. La fiecare probă **i** se oferă câte un şirag format din mai multe cristale din cele trei tipuri, într-o ordine specială şi bine gândită. Pretendentul trebuie să folosească proprietatea ce i-a fost dezvăluită pentru a determina numărul minim de cristale la care se poate ajunge în şiragul dat. El poate transforma oricare două cristale alăturate, de tipuri diferite, înlocuindu-le în şirag cu cristalul nou obţinut.

h2. Cerinţă
 
Scrieţi un program care să rezolve toate probele din testul Shamaniţei Bulbuka.
 

h2. Date de intrare

Fişierul de intrare $cristale.in$ ...

Pe prima linie a fişierului **cristale.in** se află trei caractere diferite separate prin câte un spaţiu, reprezentând cele trei tipuri de cristale. Pe a doua linie se află numărul **P** de probe din care este format testul. Fiecare dintre următoarele **P** linii conţine: **n**-numărul de cristale din şirag urmat de un spaţiu, apoi de o succesiune de **n** caractere reprezentând cristalele din şirag, în ordinea dată.

h2. Date de ieşire

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

 
În fişierul **cristale.out** se va scrie pe fiecare dintre cele **P** linii câte un număr, reprezentând numărul minim de cristale la care se poate reduce şiragul respectiv.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ P ≤ 1000$
* numărul de cristale dintr-un şirag este nenul şi nu va depăşi 100
* şiragurile sunt liniare.

h2. Exemplu