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\).

Input

• Dòng thứ nhất chứa số nguyên dương duy nhất là số bộ test \(T\) \((T \leq 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\).

Output

• 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.

Example

1
abc
ae 

2