Given are two strings S and T.

Let us change some of the characters in S so that T will be a substring of S.

At least how many characters do we need to change?

Here, a substring is a consecutive subsequence. For example, `xxx` is a substring of `yxxxy`, but not a substring of `xxyxx`.

Constraints

* The lengths of S and T are each at least 1 and at most 1000.
* The length of T is at most that of S.
* S and T consist of lowercase English letters.

Input

Input is given from Standard Input in the following format:


S
T


Output

Print the minimum number of characters in S that need to be changed.

Examples

Input

cabacc
abc


Output

1


Input

codeforces
atcoder


Output

6
#include<stdio.h>
#include<string.h>
int main()
{
	int i,j,l,c=0,d=0,m,k;
	char s[1000],t[1000];
	scanf("%s",s);
	scanf("%s",t);
	l=strlen(s),m=strlen(t);
	for(i=0;i<l-(m-1);i++)
	{
		for(j=0,k=i;j<m;j++,k++)
		{
			if(s[k]==t[j])d++;
		}
		if(d>c)c=d;
		d=0;
	}
	printf("%d",m-c);
}