No imagination at the moment.

Input

You will be given two lines. The first line will contain the string A, the second line will contain the string B. Both strings consist of no more than 50000 lowercase Latin letters.

Output

Output the length of the longest common subsequence of strings A and B.

Example

Input

abababab
bcbb

Output

3