Với mỗi xâu ký tự $X$ ta có thể thực hiện các thao tác sau đây:

• Xoá một ký tự ở vị trí bất kỳ
• Chèn thêm một ký tự vào vị trí bất kỳ
• Thay thế một ký tự bởi một ký tự khác ở vị trí bất kỳ.

Cho hai xâu ký tự $X$ và $Y$ hãy tìm cách biến đổi xâu $X$ thành xâu $Y$ với các thao tác ở trên sao cho số phép biến đổi là ít nhất.

Input

Dòng đầu là xâu $X$ không quá $1000$ ký tự in thường Tiếng Anh.

Dòng cuối là xâu $Y$ không quá $1000$ ký tự in thường Tiếng Anh.

Output:

Một số nguyên duy nhất là số phép biến đổi xâu ít nhất từ xâu $X$ thành $Y$.

Example

Input:

vo
chong

Output:

4

Giải thích: Có nhiều cách biến đổi 4 bước để chuyển xâu "vo" thành "chong" sau đây là một cách: "vo" -> "cvo" -> "cho" -> "chon" -> "chong".