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