Bessie đang sử dụng phần mềm chỉnh sửa văn bản mới nhất và tuyệt vời nhất, miV! Cô ấy bắt đầu với một chuỗi đầu vào chỉ bao gồm các chữ cái tiếng Anh viết hoa và viết thường, và cô ấy muốn biến nó thành một chuỗi đầu ra mong muốn. Với chỉ một lần nhấn phím, miV cho phép cô ấy thay thế tất cả các lần xuất hiện của một chữ cái tiếng Anh \(c_1\) trong chuỗi bằng một chữ cái tiếng Anh khác \(c_2\). Ví dụ, với chuỗi \(\texttt{aAbBaaAbBa}\), nếu Bessie chọn \(c_1\) là a và \(c_2\) là B, chuỗi ban đầu sẽ biến thành \(\texttt{BAbBBBAbBB}\).

Bessie là một con bò bận rộn, vì vậy đối với mỗi trường hợp kiểm tra độc lập \(T\) (\(1≤T≤10\)), hãy in ra số lần nhấn phím tối thiểu cần thiết để biến chuỗi đầu vào của cô ấy thành chuỗi đầu ra mong muốn.

Input

• Dòng đầu tiên chứa số nguyên \(T\), số lượng trường hợp kiểm tra độc lập.
• Tiếp theo là \(T\) cặp dòng, mỗi cặp chứa một chuỗi đầu vào và một chuỗi đầu ra có độ dài bằng nhau. Tất cả các ký tự là chữ cái tiếng Anh viết hoa hoặc viết thường (A đến Z hoặc a đến z). Tổng độ dài của tất cả các chuỗi không vượt quá \(10^5\).

Output

• Đối với mỗi trường hợp kiểm tra, hãy in ra số lần nhấn phím tối thiểu để biến chuỗi đầu vào thành chuỗi đầu ra, hoặc -1 nếu không thể thực hiện.

Scoring

• Subtask 1: Các chuỗi có độ dài không quá 50.
• Subtask 2: Tất cả các chuỗi chỉ bao gồm các chữ cái viết thường từ a đến e.
• Subtask 3: Không có ràng buộc thêm.

Example

4
abc
abc
BBC
ABC
abc
bbc
ABCD
BACD

0
-1
1
3