Biến đổi xâu ít thao tác nhất

Cho hai xâu ký tự \(A\) và \(B\). Trên xâu \(A\) được phép thực hiện các phép biến đổi sau, mỗi phép tính là một thao tác:

• Xoá một ký tự bất kỳ của \(A\);
• Chèn một ký tự bất kỳ vào một vị trí bất kỳ của \(A\);
• Thay một ký tự của \(A\) bằng một ký tự khác.

Hãy tính số thao tác ít nhất để biến \(A\) thành \(B\).

Input

• Dòng đầu chứa số nguyên \(T\) là số bộ test.
• Mỗi bộ test gồm hai dòng: dòng đầu là xâu \(A\), dòng thứ hai là xâu \(B\).

Output

Với mỗi bộ test in ra một dòng là số thao tác tối thiểu.

Constraints

• \(1 \le T \le 10\)
• Mỗi xâu chỉ gồm chữ cái in hoa, độ dài từ \(1\) đến \(2000\).

Sample Input

3
KITTEN
SITTING
ABC
ABC
AAAA
B

Sample Output

3
0
4

Explanation

KITTEN \(\to\) SITTEN (thay K bằng S) \(\to\) SITTIN (thay E bằng I) \(\to\) SITTING (chèn G): 3 thao tác. Bộ test thứ hai hai xâu giống nhau. Bộ test thứ ba: giữ lại một chữ A, thay bằng B rồi xoá 3 chữ còn lại, tổng 4 thao tác.