U541606 盾盾的打字机

盾盾有一个非常有意思的打字机，现在盾哥要用这台打字机来打出一段文章。 由于有了上次的经验，盾盾预先准备好了一段模板 $A$ 存在了内存中，并以此为基础来打出文章 $B$。盾盾每次操作可以将内存中的某一个字符改成另一个字符，或者在某一个位置插入一个字符，或者删除某一个位置上的字符。另外，为了避免自己预存的模板太腿反而浪费时间，盾哥在所有操作之前会斟酌一下选择留下模板 $A$ 的某一个最优的子串以保证操作次数尽量少（当然盾盾也可以全保留或一个都不留），这一步不计入操作次数。 试求盾盾要打出文章 $B$ 的最少操作次数。 子串是指母串中连续的一段。

输入包含多组数据。 对于每组数据，两行，分别表示 $A$ 和 $B$。

每组数据一行，一个数，表示最少操作次数。

对于 $30\%$ 的数据，满足 $\vert A\vert,\vert B\vert\leq10$。 对于 $100\%$ 的数据，满足 $\vert A\vert,\vert B\vert\leq1000$，数据组数小于等于 $10$，且输入的串中只含有小写字母。