Given a string ~S~ and a pattern ~P~ . Delete some characters in the text to form the maximum consecutive pattern strings. What is the maximum number of pattern strings can be created?

Input

• The first line is the string ~S (0 ≤ |S| ≤ 10^5)~.

• The second line is the string ~P (0 ≤ |P| ≤ 10^5)~.

• Both strings contain only lowercase characters.

Output

• A single number which is the maximum number of patterns can be created

Sample Input

abcdbacdb
acb

Sample Output

2