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


public class Main{
 public static void main(String args[]){
  Scanner scanner = new Scanner(System.in);
  String esu = scanner.next();
  String t = scanner.next();   
  int kaisu = esu.length() - t.length() + 1;
  
  //ArrayList<Integer> mat = new ArrayList<Integer>(); 
  int mat[];
  mat = new int[kaisu];
   
   for(int i=0;i<kaisu;i++){
      for(int j=0;j<t.length();j++){
        if(esu.charAt(i+j)==t.charAt(j)){
         mat[i]++;
        }else{
        }
      }  
    }
   int min =0;
   for(int i=0;i<kaisu;i++){
     if(mat[i]>min){
       min = mat[i];
     }else{
     }
   } 

  System.out.println(t.length()-min);
   
 }
}