Minimal edit distance to a string's prefix

Discription

You are given two non-empty string, str1 and str2

Return the minimum number of character edits (insert, delete, change) until str1 becomes str2's prefix.

Input

One line with 2 strings, separated by space

$1 \le str1.length() \le 2000$

$1 \le str2.length() \le 2000$

'a' <= ch <= 'z', for any ch in str1 & str2

Output

An integer

Sample input 1

abc abc

Sample output1

0

Sample input 2

ac abcd

Sample output2

1

Sample input 3

babce abcde

Sample output 3

2