Biến đổi xâu

Xem PDF

Điểm: 400 (p) Thời gian: 1.2s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho hai xâu \(S\)\(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

Test 1

Input
1
abc
ae 
Output
2

Bình luận