Longest Common Subsequence

You are given two strings s₁ and s₂. Your task is to compute the length of the Longest Common Subsequence (LCS) of these two strings.

The Longest Common Subsequence of two sequences is defined as the longest sequence that is a subsequence of both of them. Recall that a subsequence is derived from the original sequence by deleting some or no elements without changing the order of the remaining elements.

A common approach to solving this problem is by using dynamic programming. The recurrence relation used is given by:

\[ dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } s_{1}[i-1] = s_{2}[j-1], \\ \max(dp[i-1][j], dp[i][j-1]) & \text{otherwise.} \end{cases} \]

Implement a program that reads two strings from standard input and outputs the length of their longest common subsequence to standard output.

inputFormat

The input consists of two lines:

• The first line contains the string s₁.
• The second line contains the string s₂.

Both strings can consist of any printable characters. Their lengths can be assumed to be moderate.

outputFormat

Output a single integer representing the length of the longest common subsequence of the two input strings. The output should be printed to standard output.

## sample

abcde
ace

3