Bessie nutzt miV, die neueste und beste Innovation der Textbearbeitung! Sie will eine Eingabezeichenkette nur aus großen und kleinen englischen Buchstaben in eine Ausgabezeichenkette umwandeln. Ein Tastendruck ersetzt alle Vorkommen eines Buchstabens $c_1$ durch einen anderen $c_2$. Beispielsweise wird $\texttt{aAbBa}$ bei $c_1$ = a und $c_2$ = B zu $\texttt{BAbBB}$.
Bessie ist beschäftigt: Bestimme für jeden von $T$ ($1\le T\le 10$) unabhängigen Tests die kleinste Tastenzahl für die gewünschte Ausgabe.
Eingabe
Die erste Zeile enthält die Zahl unabhängiger Tests $T$.
Die nächsten $T$ Zeilenpaare geben gleich lange Ein- und Ausgabezeichenketten aus A–Z oder a–z an. Die Summe aller Zeichenkettenlängen übersteigt $10^5$ nicht.
Ausgabe
Gib je Test die kleinste Tastenzahl oder $-1$ bei Unmöglichkeit aus.
Beispiele
Eingabe 1
4 abc abc BBC ABC abc bbc ABCD BACD
Ausgabe 1
0 -1 1 3
Hinweis
Die erste Eingabe gleicht der Ausgabe: keine Taste nötig.
Die zweite ist unmöglich: Ein $\texttt{B}$ kann nicht zu $\texttt{A}$ werden, während das andere $\texttt{B}$ bleibt.
Für die dritte ersetze $\texttt{a}$ durch $\texttt{b}$.
Die letzte wird so umgewandelt: $\texttt{ABCD} \rightarrow \texttt{EBCD} \rightarrow \texttt{EACD} \rightarrow \texttt{BACD}$.
Teilaufgaben
- Eingaben 2–6: jede Zeichenkette hat Länge höchstens $50$.
- Eingaben 7–9: nur kleine $\texttt{a}$ bis $\texttt{e}$.
- Eingaben 10–15: keine weiteren Einschränkungen.
Autor der Aufgabe: Benjamin Qi