String Copy

You want to build a new string P by repeatedly copying contiguous parts of an original string S. One operation copy(s, p) takes p consecutive characters starting from the s-th character of S and appends them to the end of the string being built.

For example, if S = "abaabba" and the target string is "aaabbbabbbaaa", the operations copy(3, 2), copy(4, 3), copy(2, 2), copy(5, 2), copy(2, 3), and copy(1, 1) can build the target string in order. The intermediate string grows by appending copied parts, such as "aa", then "aaabb", then "aaabbba".

Given S and P, find the minimum number of copy operations needed to build P from S.

The first line contains the string S. The second line contains the string P.

Both strings contain only uppercase English letters, lowercase English letters, and digits. Each string has length at least 1 and at most 1,000. The input is guaranteed to be a case where P can be built from S using only copy operations.

Print the minimum number of copy operations needed to build P.