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
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    
    String s = sc.nextLine();
    String t = sc.nextLine();

    char[] schar = s.toCharArray();
    char[] tchar = t.toCharArray();

    int[] diff = new int[s.length() - t.length() + 1];

    for(int i=0; i<schar.length - tchar.length + 1; i++){
      for(int j=0; j<tchar.length; j++){
        if(schar[i + j] != tchar[j]){
          diff[i]++;
        }
      }
    }

    int min = 10000;
    for(int i=0; i<diff.length; i++){
      if(min > diff[i]){
        min = diff[i];
      }
    }

    System.out.println(min);

    return;

  }
}

