Problem D: AABABCAC

Problem

文字列$s$,$t$が与えられる。
最初、文字列集合$A=${$s$},$B=\phi$とする。
このとき、次の操作をできるだけたくさん行いたい。

操作

step1

1. $u$の全ての部分列(連続でなくてもよい)から、$t$と等しいものを任意に1つ選ぶ。選んだ部分列の$u$に対応するインデックスをそれぞれ$z_1$, $z_2$, …, $z_{|t|}$とする(ただし1 $\le$ $z_1$ $\lt$ $z_2$ $\lt$ … $\lt$ $z_{|t|}$ $\le$ $|u|$)。そのような部分列がなければ操作を終了する。


2. 選んだ部分列の文字$u_{z_1}$, $u_{z_2}$, …, $u_{z_{|t|}}$でもとの文字列を分割し、それらを$B$に追加する。

例えば、$u=$"abcdcd", $t=$"ac"の場合は次の2通りの分割の方法が考えられる。
$u$の1番目の文字と3番目の文字を選んだ場合、""と"b"と"dcd"に分割される。
$u$の1番目の文字と5番目の文字を選んだ場合、""と"bcd"と"d"に分割される。

step2

部分列の例

"abac"の部分列は、 { "" , "a" , "b" , "c" , "aa" ,"ab" , "ac" , "ba" , "bc" , "aac" , "aba" , "abc" , "bac" , "abac" } である。
"a"は"abac"の1文字目、または3文字目を抜き出すことによってできた部分列である。
"ac"は"abac"の1文字目と4文字目、または3文字目と4文字目を抜き出すことによってできた部分列である。

Input

入力は以下の形式で与えられる。

$s$
$t$

1行目に文字列$s$,2行目に文字列$t$が与えられる。

Constraints

入力は以下の条件を満たす。

• 1 $\le$ $|t|$ $\le$ $|s|$ $\le$ $10^5$
• 文字列$s$,$t$に含まれる文字はアルファベットの大文字または小文字

Output

操作回数の最大値を出力せよ。

Sample Input 1

AABABCAC
A

Sample Output 1

2

1回目の操作は、$A=${ "AABABCAC" }で始まる。
step1では、$u=$"AABABCAC"に対して、例えば4番目の文字を$t$と等しい部分列として選び、"AAB"と"BCAC"に分割し、それらを$B$に追加する。
step2では、$A$を$B$に置き換え、$B$を空にし、操作回数は1となる。

2回目の操作は、$A=${ "AAB" , "BCAC" }で始まる。
step1では、$u=$"AAB"に対して、例えば1番目の文字を$t$と等しい部分列として選び、""と"AB"に分割し、それらを$B$に追加する。次に$u=$"BCAC"に対して、3番目の文字を$t$と等しい部分列として選び、"BC"と"C"に分割し、それらを$B$に追加する。
step2では、$A$を$B$に置き換え、$B$を空にし、操作回数は2となる。

3回目の操作は、$A=${ "" , "AB" , "BC" , "C" }で始まる。
step1では、$u=$""に対して、$t$と等しい部分列が存在しないため、ここで操作を終了する。

この例の場合、3回目の操作ではstep1で操作が終了したため、操作回数は2となる。

Sample Input 2

abaabbabaabaabbabbabaabbab
ab

Sample Output 2

3

Sample Input 3

AbCdEfG
aBcDeFg

Sample Output 3

0