Cho hai xâu, hãy tìm cách biến đổi xâu thứ nhất thành xâu thứ hai sao cho sử dụng ít phép biến đổi nhất: chèn, sửa, xóa.

Dữ liệu vào

Dòng đầu tiên chứa duy nhất một số T ≤ 30 là số lượng bộ test.
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á 1500.

Kết quả

Ghi ra T dòng, mỗi dòng là kết quả tương ứng cho một test là số lượng phép biến đổi tìm được.