Shortest Uncommon Subsequence

Time limit

Memory limit

128 MB

Problem

A subsequence of string A is made by choosing one or more characters from A and writing them in their original relative order. The chosen characters do not have to be adjacent.

Given two strings A and B, find the length of the shortest string that is a subsequence of A but is not a subsequence of B.

Input

The first line contains string A, and the second line contains string B. Both strings consist only of lowercase English letters, and each length is at most 1000. Every input is guaranteed to have an answer.

Output

Print the length of the shortest string that is a subsequence of A but not a subsequence of B.