Longest Common Subsequence

Given two strings str1 and str2, your task is to compute the length of their longest common subsequence (LCS). A subsequence is a sequence that appears in the same relative order in both strings, but not necessarily contiguously.

For example, if str1 = "abcde" and str2 = "ace", the longest common subsequence is "ace" with a length of 3.

The dynamic programming recurrence relation used to solve this problem is given by: $$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1, & \text{if } str1[i-1] = str2[j-1] \\ \max(dp[i-1][j],\; dp[i][j-1]), & \text{otherwise} \end{cases}$$

Your program should read input from stdin and write the result to stdout.

inputFormat

The input consists of two lines. The first line contains the string str1, and the second line contains the string str2.

outputFormat

Output a single integer representing the length of the longest common subsequence of the two strings.## sample

abcde
ace

3