说明

　　有二个字串 str1, str2 , 字串str2 可以经过若于次变换后变成str1，其变换的规则是：

　　1） 可以在任何位置加入字符；

　　2） 可以删除任何字符；

　　3） 可以改变任何字符。

　　约定：增加、删除与改变任何一个字符称为一次变换。

　　例如：str1=‘bcadef ’           str2=’abcedkk’ 

　　可以经过的变换为：

　　1）删去第一个字符‘a’                     str2=’bcedkk’

　　2）改变一个字符，将‘e’变成‘a’          str2=’bcadkk’

　　3）改变一个字符，将‘k’变成‘e’          str2=’bcadek’

　　4） 改变一个字符，将‘k’变成‘f’          str2=’bcadef’

　　此时，str2 经过4次变换后变成str1。

　　问题：给出str1，str2，要求用最少的变换次数从str2变换为str1 。

输入格式

　　多笔测资，每笔测资两行

　　第一行：字符串s1

　　第二行：字符串s2

输出格式

样例

bcadef
abcedkk

4

提示