Edit

题目描述

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

提示

动态规划