Cho hai xâu \(S\) và \(T\) chỉ gồm các ký tự in thường. Bạn được phép thực hiện một trong ba thao tác sau trên xâu \(S\):

• Chèn một ký tự bất kỳ vào xâu.
• Xoá một ký tự bất kỳ trong xâu.
• Thay đổi một ký tự bất kỳ trong xâu thành ký tự in thường khác.

Yêu cầu

• Tìm số thao tác ít nhất để đưa xâu \(S\) về xâu \(T\)

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên dương duy nhất là số bộ test \(T\) \((T \le 40)\)
• Mỗi test gồm \(2\) dòng, mỗi dòng chứa một xâu gồm các kí tự trong 'a' đến 'z' viết liền nhau, giới hạn độ dài không quá \(10^3\)

Dữ liệu ra

• Ghi ra \(T\) dòng, mỗi dòng là kết quả tương ứng cho một test là số thao tác ít nhất.

Input 1

1
abc
ae

Output 1

2