Bessie dùng miV, đổi mới mới nhất và tuyệt nhất của phần mềm soạn văn bản! Nó muốn đổi xâu đầu vào chỉ gồm chữ Anh hoa và thường thành xâu đầu ra. Một lần nhấn phím thay mọi lần xuất hiện của chữ $c_1$ bằng chữ Anh khác $c_2$. Ví dụ $\texttt{aAbBa}$ với $c_1$ = a, $c_2$ = B thành $\texttt{BAbBB}$.

Bessie bận rộn; với mỗi trong $T$ ($1\le T\le 10$) bộ kiểm tra độc lập, tìm số lần nhấn ít nhất để đổi đầu vào thành đầu ra muốn có.

Dữ liệu vào

Dòng đầu chứa số bộ kiểm tra độc lập $T$.

$T$ cặp dòng tiếp chứa xâu vào và ra cùng độ dài, chữ A–Z hoặc a–z. Tổng độ dài tất cả xâu không vượt $10^5$.

Dữ liệu ra

Với mỗi bộ, in số lần nhấn ít nhất, hoặc $-1$ nếu không thể.

Ví dụ

Dữ liệu vào 1

4
abc
abc
BBC
ABC
abc
bbc
ABCD
BACD

Dữ liệu ra 1

0
-1
1
3

Ghi chú

Xâu vào đầu tiên giống xâu ra nên không cần nhấn phím.

Xâu thứ hai không thể đổi một $\texttt{B}$ thành $\texttt{A}$ mà giữ $\texttt{B}$ kia.

Xâu thứ ba đổi $\texttt{a}$ thành $\texttt{b}$.

Xâu cuối đổi như sau: $\texttt{ABCD} \rightarrow \texttt{EBCD} \rightarrow \texttt{EACD} \rightarrow \texttt{BACD}$.

Nhiệm vụ con

• Đầu vào 2–6: mỗi xâu dài không quá $50$.
• Đầu vào 7–9: chỉ chữ thường $\texttt{a}$ đến $\texttt{e}$.
• Đầu vào 10–15: không thêm ràng buộc.

Tác giả bài toán: Benjamin Qi