Cho hai xâu \(X\) và \(Y\) 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 \(X\):

• 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 \(X\) về xâu \(Y\).

Input

• Dòng thứ nhất chứa số nguyên dương duy nhất là số bộ test \(T (T≤40).\)

• Với mỗi test gồm 2 dòng, dòng thứ nhất chứa xâu \(X\), dòng thứ hai chứa xâu \(Y (|X|,|Y|≤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.

Sample Input

1
dcs
dt

Sample Output

2