Description

Given two strings S and T, where the length of S is guaranteed to be no less than that of T, determine the minimum number of characters in S that need to be modified so that T becomes a subsequence of S.

Input Format

The input consists of two lines:

The first line contains string S, and the second line contains string T.

It is guaranteed that the length of S is no less than that of T, and the length of S ranges between 10 and 1000.

Output Format

The minimum number of characters in S that need to be modified.

```input1 ABCDABCD AABCX

```output1
1

ABCDABCD
XAAD

2

XBBBBBAC
ACC

2

Hint

Example 1: Change S: ABCDABCD to ABCDABCX. (I understand that a subsequence means S contains all elements of T in order, not necessarily consecutively.) (Also not sure if the styling will remain, bolded parts are T, underlined parts are modified.)

Example 2:

Original: ABCDABCD

Modified: XACDABCD

Example 3:

Original: XBBBBBAC

Modified: ABBBBBCC

(In Example 3, A can replace any of the preceding B's or X. For example: XABBBBCC)

Source

2019 10th Lanqiao Cup C/C++ Group B National Finals