A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters. For example: abc is a subsequence of abbac.

You are given two strings ~s~ and ~t~ consisting of only lowercase English letters. Find the minimum number of characters that need to be appended to the end of ~s~ so that ~t~ becomes a subsequence of ~s~.

Input

• The first line is the string ~s~ ~(0 ≤ |s| ≤ 10^5)~.

• The second line is the string ~t~ ~(0 ≤ |t| ≤ 10^5)~.

• Both strings contain only lowercase characters.

Output

• The minimum number of characters that need to be appended to the end of ~s~ so that ~t~ becomes a subsequence of ~s~.

Sample Input 1

abbac
abc

Sample Output 1

0

Sample Input 2

baac
abc

Sample Output 2

2

Sample Input 3

aaaaa
abc

Sample Output 3

2

Sample Input 4

abcabc
cba

Sample Output 4

1

Notes:

• In the first sample, ~t~ is already a subsequence of ~s~, so there is no need to add any characters.

• In the second and the third samples, bc should be added to ~s~

• In last sample, a should to be added to ~s~.