Bessie utilise miV, la dernière et meilleure innovation en édition de texte ! Elle veut transformer une chaîne d’entrée composée de lettres anglaises majuscules et minuscules en une chaîne de sortie. Une touche suffit pour remplacer toutes les occurrences d’une lettre $c_1$ par une autre $c_2$. Ainsi $\texttt{aAbBa}$ avec $c_1$ = a et $c_2$ = B devient $\texttt{BAbBB}$.
Bessie est occupée ; pour chacun des $T$ ($1\le T\le 10$) tests indépendants, affichez le nombre minimal de touches pour obtenir la sortie voulue.
Entrée
La première ligne contient le nombre de tests indépendants $T$.
Les $T$ paires de lignes suivantes donnent entrée et sortie de même longueur, avec des lettres A–Z ou a–z. La somme des longueurs de toutes les chaînes ne dépasse pas $10^5$.
Sortie
Pour chaque test, affichez le nombre minimal de touches ou $-1$ si la transformation est impossible.
Exemples
Entrée 1
4 abc abc BBC ABC abc bbc ABCD BACD
Sortie 1
0 -1 1 3
Remarque
La première entrée égale la sortie : aucune touche nécessaire.
La deuxième est impossible : on ne peut changer un $\texttt{B}$ en $\texttt{A}$ tout en gardant l’autre $\texttt{B}$.
La troisième s’obtient en changeant $\texttt{a}$ en $\texttt{b}$.
La dernière se transforme ainsi : $\texttt{ABCD} \rightarrow \texttt{EBCD} \rightarrow \texttt{EACD} \rightarrow \texttt{BACD}$.
Sous-tâches
- Entrées 2–6 : longueur de chaque chaîne au plus $50$.
- Entrées 7–9 : seulement les minuscules $\texttt{a}$ à $\texttt{e}$.
- Entrées 10–15 : aucune contrainte supplémentaire.
Auteur du problème : Benjamin Qi