Berland有着悠久而辉煌的历史。为了提高年轻公民对此的认识,贝尔兰国王决定创作一首国歌。
虽然贝尔兰德历史上有很多很多的胜利,但其中最引人注目的是一场。金希望在国歌中尽可能多地提及这一点。
他已经创作了国歌的主要部分,现在只需要填写一些字母。金请你帮助他完成这项工作。
国歌是由不超过 105 个小拉丁字母和问号组成的字符串 s。最辉煌的胜利是由不超过105个小拉丁字母组成的字符串t。您应该将所有问号替换为小拉丁字母,以使字符串 t 在字符串 s 中出现的次数最多。
请注意,字符串 t 在 s 中的出现可以重叠。检查第三个示例以进行澄清。
输入
第一行包含小拉丁字母和问号 s 的字符串 (1 ≤ |s| ≤ 105)。
第二行包含小拉丁字母串 t (1 ≤ |t| ≤ 105)。
字符串长度的乘积 |s|·|t|不会超过107。
输出
输出字符串 t 出现的最大次数,将字符串 s 中的所有问号替换为小拉丁字母即可实现。
示例
输入 #1
winlose???winl???w?? win
输出 #1
5
输入 #2
glo?yto?e??an? or
输出 #2
3
输入 #3
??c????? abcab
输出 #3
2
注意
在第一个示例中,结果字符串 s 是“winlosewinwinlwinwin”
在第二个示例中,结果字符串 s 是“glorytoreorand”。字符串的最后一个字母可以是任意的。
在第三个示例中,字符串 t 的出现是重叠的。 t 出现次数最多的字符串 s 是“abcabcab”。