SPOJ Problem Set (classical) 704. Remove The String Problem code: PSTRING

Given two strings X and Y, your task is find the minimum number of characters to be removed from X in order to obtain a string X' that does not contain Y as a substring.

Input

Input contains some test cases. Each test cases contains two lines, First is X and second is Y. Length of X <= 10000, Length of Y <= 1000.

Output

For each test cases, You should output exactly one integer is the minimum number of characters to be remove

Example

Input:
ababaa
aba

Output:
1

---

Added by:	Hoang Hong Quan
Date:	2006-01-17
Time limit:	3s
Source limit:	50000B
Languages:	All except: CLOJ F# PERL 6 TECS
Resource:	A contest of Romanian