Description

设s1和s2是两个字符串, 经过一些操作，我们可以将字符串s1转换为字符串s2, 这里所说的字符操作包括: (1)删除一个字符; (2)插入一个字符; (3)将一个字符改为另一个字符. 将字符串s1转换为字符串s2所用的最少字符操作数称为字符串s1到字符串s2的编辑距离, 它描述了s1和s2的近似程度.

Input

输入有多组,每组2行字符串,分别为s1,s2,均不为空,长度不大于1000.

Output

对于每组输入,输出最小编辑距离.

Sample

Input

abc
ABC
abc
cba

Output

3
2

Source: 仙剑魔