问题描述

给定两个字符串 $A$ 和 $B$，请你求出它们的最长公共子序列（Longest Common Subsequence，简称 LCS）的长度。

子序列是指从一个字符串中删除若干个字符（也可以不删除）后，保持剩余字符相对顺序不变得到的新字符串。

例如，字符串 "ace" 是 "abcde" 的一个子序列，但 "aec" 不是 "abcde" 的子序列。

公共子序列是指同时是字符串 $A$ 和字符串 $B$ 的子序列的字符串。

请你求出最长公共子序列的长度。

输入格式

输入共两行。

第一行包含一个字符串 $A$。

第二行包含一个字符串 $B$。

输出格式

输出一个整数，表示字符串 $A$ 和字符串 $B$ 的最长公共子序列的长度。

样例输入

abcde
ace

样例输出

3

说明

字符串 "ace" 是 "abcde" 和 "ace" 的公共子序列，长度为 $3$。

例如：

"a" 是公共子序列，长度为 $1$

"ac" 是公共子序列，长度为 $2$

"ace" 是公共子序列，长度为 $3$

因此最长公共子序列长度为 $3$。

评测数据规模

对于所有数据，满足：

$1 \le |A|, |B| \le 1000$

字符串仅包含小写英文字母。