题目描述

给定两个字符串 $S$ 和 $T$。

我们需要改变 $S$ 中的一些字符，使得 $T$ 成为 $S$ 的子串。

至少需要改变多少个字符？

这里，子串是连续的子序列。例如，xxx 是 yxxxy 的一个子串，但不是 xxyxx 的子串。

约束条件

• 字符串 $S$ 和 $T$ 的长度分别为 $1$ 到 $1000$。
• 字符串 $T$ 的长度不超过 $S$ 的长度。
• 字符串 $S$ 和 $T$ 由小写英文字母组成。

输入

输入以以下格式从标准输入中给出：

$S$

$T$

输出

输出需要改变的最小字符数量。

示例输入 1

cabacc
abc

示例输出 1

1

例如，将 $S$ 中的第四个字符 a 改为 c，可以将 $S$ 的第二到第四个字符与 $T$ 匹配。

由于 $S$ 本身不是 $T$ 的子串，所以改变一个字符就是最小需要的。

示例输入 2

codeforces
atcoder

示例输出 2

6