题目描述

母牛贝西安排了一串 $\red{N }$块石头，每块石头都包含一个字母，她想把它做成一条时尚的项链。

为了保护她的财物，贝西不想与目前住在她身边的另一头奶牛分享她的项链。另一头母牛的名字是一个由 $\red{M }$个字符组成的字符串，$\red{Bessie }$希望确保这个长度为 $\red{M }$的字符串不会作为连续子字符串出现在代表她的项链的字符串中的任何位置（否则，另一头母牛可能会错误地认为项链是给她的）。$\red{Bessie }$决定移除她项链中的一些石头，这样另一头母牛的名字就不会作为子字符串出现。请帮助 $\red{Bessie }$确定她必须移除的最少石块数量。

贝西收集了$\red{N}$颗石头，每颗石头上都有一个字母，贝西想把这些石头做成项链。

贝西的身边有另一只奶牛，这只奶牛的名字是一个长度为$\red{M}$的字符串，贝西不希望这只牛的名字出现在她的项链上$\red{(}$项链的子串$\red{)，}$她想知道，最少删掉几颗石头就可以避免这种情况发生。

输入格式

第 $\red{1 }$行：第一行是长度为 $\red{N }$的字符串，描述 $\red{Bessie }$最初的项链；每个字符都在"$\red{a}$"到"$\red{z}$"的范围内。

第 $\red{2 }$行：第二行是谷仓中另一头牛的长度为 $\red{M }$的名称，也是由"$\red{a}$"到"$\red{z}$"的字符组成。

输出格式

第 $\red{1 }$行：需要从 $\red{Bessie }$的项链中移除的最小宝石数，以便它不包含另一头牛的名字作为子字符串。

样例

输入样例

阿巴巴
阿坝

输出样例

1

提示

For at least 20% of test cases, N <= 20.
For at least 60% of test cases, N <= 1000, M <= 100.
For all test cases, N <= 10000, M <= 1000.
For all test cases, M <= N.

修改后的项链应该是"$\red{abbaa}$"。