Xét các xâu chỉ gồm các ký tự ‘a’->’z’. Từ xâu x có thể biến đổi trực tiếp thành xâu y nếu tồn tại một xâu z thỏa mãn 2 điều kiện sau:

- xâu z nhận được từ xâu x bằng cách xóa đi không quá một nửa số ký tự của x;
- xâu z nhận được từ xâu y bằng cách xóa đi không quá một nửa số ký tự của y.

Ví dụ: x=‘abcdef’ có thể biến đổi được thành xâu y=‘apcqd’ vì tồn tại xâu z=‘acd’ .

Yêu cầu: cho 2 xâu s và t, hãy tìm số phép biến đổi ít nhất từ xâu s thành xâu t.

Input

- Dòng 1: xâu s,
- Dòng 2: xâu t.

Độ dài mỗi xâu không vượt quá 200

Output

- Gồm 1 dòng chứa một số là số phép biến đổi ít nhất tìm được.