Minimum Modifications to Include Subsequence

We say that a string \(S\) "contains" a string \(T\) if \(T\) is a subsequence of \(S\). That is, \(T\) can be obtained by deleting some (possibly zero) characters from \(S\) without changing the order of the remaining characters.

Given two strings \(S\) and \(T\), determine the minimum number of characters in \(S\) that need to be modified so that \(S\) contains \(T\) as a subsequence. In one modification, you can change any character in \(S\) to any other character.

Note: It is guaranteed that the length of \(S\) is greater than or equal to the length of \(T\).

inputFormat

The input consists of two lines. The first line contains the string \(S\) and the second line contains the string \(T\).

outputFormat

Output a single integer, the minimum number of modifications required to make \(S\) contain \(T\) as a subsequence.

sample

abcde
ace

0