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.

Input

• Dòng đầu chứa số nguyên \(T≤30\) là số 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ự chữ cái la tinh in thường viết liền nhau, độ dài mỗi xâu không quá 1500.

Output

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

Sample Input

1
eda
f

Sample Input

3