similar

Similar

Gigel vrea să verifice cât de similare sunt $P$ şi $T$.
El verifică similaritatea transformând şirul $P$ în şirul $T$ prin următoarele operaţii:

* transformă caracterul $?$ în $0$ sau în $1$, plătind $0$ RON în costuri de similaritate
* transformă caracterul $*$ într-un şir de $0$ şi $1$, plătind 0 RON în costuri de similaritate
* transformă caracterul $0$ în $1$, plătind $1$ RON în costuri de similaritate
* transformă caracterul $1$ în $0$, plătind $1$ RON în costuri de similaritate

Gradul de similaritate între $P$ şi $T$ este dat de cel mai mic preţ cu care se poate transforma $P$ în $T$. Gigel vă roagă să-l ajutaţi să găsească
gradul de similaritate.

Gradul de similaritate între $P$ şi $T$ este dat de cel mai mic preţ cu care se poate transforma $P$ în $T$. Gigel vă roagă să-l ajutaţi să găsească gradul de similaritate.

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$.

Pe prima linie din fişierul de intrare $similar.in$ se găseşte numărul $Z$ de teste. Pe următoarele $Z * 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$.

h2. Date de ieşire

h2. Restricţii

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

* pentru fiecare test, $P$ şi $T$ au cel puţin $1$ caracter şi cel mult $1000$ de caractere
* $1$ ≤ $Z$ ≤ $512$

h2. Exemplu

h3. Explicaţie

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

În primul test, $*$ se transformă în şirul $01$ (cost 0). În al doilea test, fiecare $?$ se transformă în $1$ (cost $0$) şi cei doi de $0$ se transformă în $1$ (cost $2$). Pentru ultimul test, $0$ nu se poate transforma în $01$.

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

9904