Rishi likes to play with strings.Strings have been his passion since his childhood.One day in college,Rishi came to know about the contest - International Strings Olympiad.Since then he has been determined to work on his passion and win the Olympiad.
Today Rishi has got stuck in an interesting problem.Help him solve that.

Given two strings str1 and str2 and below operations that can performed on str1. Find minimum number of operations required to convert ‘str1′ into ‘str2′.

The operations can be any of the following types:

->Insert

->Remove

->Replace

All of the above operations are of equal cost.

Input

The first line contains string str1 (length of str1 is ≤140)

The second line contains string str2 (length of str2 is ≤140)

Output

Print minimum number of operations required to convert ‘str1′ into ‘str2′.

SAMPLE INPUT
rish
rishi

SAMPLE OUTPUT
1

Explanation

We can convert rish into rishi by inserting a 'i'

见题面

见题面