h2. Date de intrare

Pe prima linie din fişierul de intrare $similar.in$ se găseşte numărul $T$ de teste. Pe următoarele $T * 2$ linii se găsesc testele, fiecare test pe două linii. Pe prima linie dintr-un test e şirul $T$ şi pe a doua linie şirul $P$.

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

h2. Date de ieşire

Pentru fiecare test, afişaţi în fişierul de ieşire $similar.out$ câte o linie cu un număr reprezentând costul minim de similaritate plătit de Gigel. Dacă nu se poate face transformarea, afişaţi $-1$.

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

h2. Restricţii

* pentru fiecare test, $P$ şi $T$ au cel mult $1000$ de caractere
* $1$ ≤ $T$ ≤ $512$

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

h2. Exemplu
table(example). |_. similar.in |_. similar.out |

| 3
0101
0*1
1111
??00
01
1
| 0
2
-1

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

În primul test, $*$ se transformă în şirul $01$ (cost 0). În al doilea

...

== include(page="template/taskfooter" task_id="similar") ==