Truyền tin

Cho một xâu $s$ gồm các chữ cái Latin thường. Ta gọi $t$ là một xâu con liên tiếp bất kỳ của $s$ (chọn một đoạn liên tiếp trong $s$, đoạn này có thể có độ dài từ $1$ đến $|s|$).

Sau khi chọn $t$, ta được phép thực hiện một số lần biến đổi (có thể không thực hiện lần nào) để đưa $t$ về đúng bằng một xâu đích $u$ cho trước. Mỗi lần biến đổi là một trong ba thao tác:

• Thêm một chữ cái vào một trong hai đầu của xâu.
• Xóa một chữ cái ở một trong hai đầu của xâu.
• Thay một chữ cái thành một chữ cái khác bất kỳ.

Với mỗi xâu con $t$ đã chọn, ta luôn thực hiện số lần biến đổi ít nhất có thể để thu được $u$. Hãy chọn xâu con $t$ sao cho số lần biến đổi cần thiết là nhỏ nhất, và in ra số lần biến đổi nhỏ nhất đó.

Dữ liệu vào

• Dòng thứ nhất chứa xâu $s$.
• Dòng thứ hai chứa xâu $u$.

Cả hai xâu đều khác rỗng và chỉ gồm các chữ cái Latin thường.

Dữ liệu ra

• In ra một số nguyên duy nhất: số lần biến đổi nhỏ nhất cần thực hiện.

Ràng buộc

• $1\le |s|,|u|\le 2000$

Ví dụ