Minimum Operations to Make a Subsequence

You are given two strings S and T. Your task is to determine the minimum number of operations required to modify S so that it becomes a subsequence of T.

Allowed operations:

• Insert any character at any position in S.
• Delete any character from S.

A string A is a subsequence of string B if all characters of A can be found in B in the same order (not necessarily contiguous). For example, ABC is a subsequence of AXBYC.

In this problem, you only need to perform deletion operations if necessary. The reason is that by deleting the appropriate characters from S, you can always obtain a subsequence that already appears in T. In particular, the minimum number of operations required is given by \[ \text{operations} = |S| - \text{LCS}(S, T), \] where \( \text{LCS}(S, T) \) denotes the length of the Longest Common Subsequence of S and T, and \(|S|\) is the length of S.

It is guaranteed that T is non-empty and the given strings contain only uppercase English letters.

inputFormat

The first line contains the string S.

The second line contains the string T.

Both strings consist of uppercase English letters.

outputFormat

Output a single integer — the minimum number of operations required to make S a subsequence of T.

## sample

ABAC
BAACA

1