Дано два рядки ~S~ та ~T~. Знайдіть мінімальну кількість операцій, необхідних для перетворення ~S~ на ~T~.

Дозволені операції:

• вставка одного символу;
• видалення одного символу;
• заміна одного символу на інший.

Вхідні дані

Перший рядок містить рядок ~S~ (~0 \le |S| \le 200~).

Другий рядок містить рядок ~T~ (~0 \le |T| \le 200~).

Рядки складаються з маленьких латинських літер (можуть бути порожніми).

Вихідні дані

Виведіть одне ціле число — мінімальну редакційну відстань між ~S~ та ~T~.

Приклад

Вхідні дані

kitten
sitting

Вихідні дані

3

Пояснення:
kitten → sitten (заміна) → sittin (заміна) → sitting (вставка).