Longest Common Subsequence (LCS)

Time Limit	Memory	Input	Output
1 s	64 MB	stdin	stdout

Time Limit

Memory

Input

Output

1 s

64 MB

stdin

stdout

A classic 2D DP problem. Try to define what dp[i][j] should mean before writing any code.

Given two strings, find the length of the longest common subsequence between them.

A subsequence is a sequence of characters obtained by deleting zero or more characters from a string, without changing the order of the remaining characters (the characters don't have to be next to each other). A common subsequence of two strings is a subsequence that appears in both of them.

Input

First line of input will be the string $s_{1}$ .
In the second line will be the string $s_{2}$ .

Output

A single number - the length of the longest common subsequence of $s_{1}$ and $s_{2}$ .

Example

Input

abcde
ace

Output

The longest common subsequence is ace, with a length of 3.

Constraints

1 \leq ∣ s_{1} ∣, ∣ s_{2} ∣ \leq 1000

Both strings consist of lowercase English letters.

Input

Output

Example

Constraints

Submit your solution