A string is a subsequence of another string if it can be constructed from the string by removing some of its characters. Given two strings, compute the length of their longest common subsequence.

Input

The input contains two lines, the first line contains a string of length n and the second line contains a string of length m. The strings consist of lowercase English letters.

Output

Output the length of the longest common subsequence of the strings.

Constraints

• 1 \le n \le 10^6
• 1 \le m \le 10^3

Example

Input:

apina
apila

Output:

4

The longest common subsequence is "apia"

Input:

abcdefghijklmnopqrstuvwxyz
bbddee

Output:

3

The longest common subsequence is "bde"