Description

Write a program to compute the Longest Common Subsequence (LCS).
A subsequence of a sequence is obtained by deleting some characters from the original sequence.
For example, aed is a subsequence of bacedf.
The longest common subsequence of two sequences is the common subsequence with the greatest length.
For instance, ade is one of the longest common subsequences of abcde and zzadfess.

Use the following recursive algorithm to compute the length of the LCS:

• If the first characters of both strings are the same,
  the length of the LCS is 1 plus the LCS length of the two strings with their first characters removed.

• If the first characters are different,
  the LCS length is the maximum of the following two results:

  1. The LCS length after removing the first character from the first string.

  2. The LCS length after removing the first character from the second string.

Constraints:
0 < n ≤ 16

Input

Two lines, each containing a lowercase letter string of length ≤ n.

Ex. abcde
zzadfess

Output

The length of the longest common subsequence.

Ex. 3

Sample Input  Download

Sample Output  Download

Discuss