Условие недоступно на русском языке
A. 最大子串匹配删除操作
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

给定两个字符串 S 和 T ，每回合，你可以执行以下两种操作之一，直到 T 变为空字符串：

  1. 删除操作：删除字符串 T 开头的第一个字符。
  2. 匹配删除操作：如果在 S 中存在一个子串 S[i, j] 与当前的 T 完全相同，则可以删除 S 的前缀 S[1, j]（即保留 S[j + 1, |S|]），同时删除字符串 T 开头的第一个字符。

你的目标是计算 最多 可以执行多少次匹配删除操作。

Input

第一行和第二行分别输入仅由小写英文字母构成的字符串 S 和 T（1 ≤ |S|, |T| ≤ 2 × 105）。

Output

输出一个整数，表示最多可以执行匹配删除操作的次数。

Examples
Input
abcb
aab
Output
2
Input
ddddddd
dddd
Output
3
Input
lovelloovvee
love
Output
3
Input
hahahahahaha
haha
Output
4
Input
acmer
medal
Output
0
Input
treewithsegmentcalledsegmenttree
segment
Output
3
Note

在第一个测试样例中，按如下顺序操可以执行最多次数的匹配删除操作：

  • T="aab"，S="abcb"，执行删除操作。
  • T="ab"，S="abcb"，执行匹配删除操作，匹配 S[1, 2]。
  • T="b"，S="cb"，执行匹配删除操作，匹配 S[2, 2]。

然后字符串 S 和字符串 T 均为空，无法再执行任何操作。