题目描述

有二个字串 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