Bessie usa miV, a mais recente e melhor inovação em edição de texto! Quer transformar uma cadeia de entrada de letras inglesas maiúsculas e minúsculas numa de saída. Uma tecla substitui todas as ocorrências de uma letra $c_1$ por outra $c_2$. Por exemplo, $\texttt{aAbBa}$ com $c_1$ = a e $c_2$ = B torna-se $\texttt{BAbBB}$.
Bessie está ocupada; para cada um dos $T$ ($1\le T\le 10$) testes independentes, calcule o mínimo de teclas para obter a saída desejada.
Entrada
A primeira linha contém o número de testes independentes $T$.
Os $T$ pares de linhas seguintes dão entrada e saída de igual comprimento, com letras A–Z ou a–z. A soma dos comprimentos de todas as cadeias não excede $10^5$.
Saída
Para cada teste, imprima o mínimo de teclas, ou $-1$ se for impossível.
Exemplos
Entrada 1
4 abc abc BBC ABC abc bbc ABCD BACD
Saída 1
0 -1 1 3
Nota
A primeira entrada é igual à saída, sem teclas necessárias.
A segunda é impossível: não se pode mudar um $\texttt{B}$ para $\texttt{A}$ mantendo o outro $\texttt{B}$.
A terceira obtém-se mudando $\texttt{a}$ para $\texttt{b}$.
A última transforma-se assim: $\texttt{ABCD} \rightarrow \texttt{EBCD} \rightarrow \texttt{EACD} \rightarrow \texttt{BACD}$.
Subtarefas
- Entradas 2–6: cada cadeia tem comprimento máximo $50$.
- Entradas 7–9: só minúsculas $\texttt{a}$ a $\texttt{e}$.
- Entradas 10–15: sem restrições adicionais.
Autor do problema: Benjamin Qi