刘老师给出两个小写字符串 $S$ 和 $T$，其中 $T$ 不长于 $S$。小珅可以把 $S$ 中的一些字符改成其他小写字母，希望修改后 $T$ 能作为 $S$ 的连续子串出现。

连续子串必须占据一段相邻位置。例如，xxx 是 yxxxy 的连续子串，却不是 xxyxx 的连续子串。系统需要计算最少修改字符数。

小婷老师只允许替换字符，不允许插入、删除或打乱 $S$。因此每一种方案都对应把完整的 $T$ 对齐到 $S$ 的某个等长连续区间。

输入格式

第一行输入字符串 $S$，第二行输入字符串 $T$。

输出格式

输出为了让 $T$ 成为 $S$ 的连续子串，至少需要修改 $S$ 中多少个字符。

cabacc
abc

1

codeforces
atcoder

6

aaaa
a

0

样例解释

样例 #1

把 $T$ 与 $S$ 的第 $2$ 到第 $4$ 个字符对齐时只需修改一个字符，且无法做到零次。

样例 #2

枚举所有可对齐位置后，最小的不相同字符数为 $6$。

样例 #3

a 已经是 $S$ 的连续子串，不需要修改。

数据范围与约定

• $1 \le |S|,|T| \le 1000$
• $|T|\le |S|$
• $S,T$ 只包含小写英文字母