Migrated from Lutece 3050 我承认阁下的字符串匹配很强

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

“我承认阁下的字符串匹配很强，但是假如，我是说假如，我的字符串里有通配符，阁下又该如何应对呢？”

给定一个字符串 $S$ , 包含小写字母和问号，其中每个问号都可以替换成任意一个小写字母，你需要构造一个方案，最大化字符串 $T$ 在 $S$ 出现的次数。

字符串 $T$ 在 $S$ 中的匹配可以重叠（参考样例）。

Input

第一行一个字符串 $S$，保证 $S$ 中只包含小写字母和问号；

第二行一个字符串 $T$，保证 $T$ 中只包含小写字母。

Output

一行一个整数，表示字符串 $T$ 在 $S$ 出现次数的最大值。

Samples

??c?????
abcab

2

Constraints

$1 \leq|S| \leq 10^5$；

$1 \leq|T| \leq 10^5$；

两个字符串长度的乘积不大于 $10^7$ , 即 $|S| \cdot |T|\leq 10^7$。

Note

样例中，当 $S$ 被确定为 abcabcab 时，$T$ 的出现次数为 $2$ 次。可以证明没有 $T$ 出现次数更多的方案。

Resources

2023 UESTC ICPC Training for String