题目描述

字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列 $X=\{x_0,x_1,\cdots ,x_{m-1}\}$，序列 $Y=\{y_0,y_1,\cdots ,y_{k-1}\}$ 是 $X$ 的子序列，当且仅当存在 $X$ 的一个严格递增下标序列 $\{i_0,i_1,\cdots,i_{k-1}\}$，使得对所有的 $j=0,1,\cdots,k-1$，有 $x_{i_j}=y_j$。例如，$X=\verb!"ABCBDAB"!$，$Y=\verb!"BCDB"!$ 是 $X$ 的一个子序列。对给定的两个字符序列，求出他们最长的公共子序列长度。其中，两个子序列 $i$ 和 $j$ 不同，当且仅当长度不同或子序列中 $\exist k, i_k \neq j_k$。

输入格式

第一行为第一个字符序列，都是大写字母组成，以 . 结束，大写字母个数不超过 $5000$。

第二行为第二个字符序列，都是大写字母组成，以 . 结束，大写字母个数不超过 $5000$。

输出格式

第一行输出上述两个最长公共子序列的长度。

样例

样例输入 1

ABCBDAB.
BACBBD.

样例输出 1

4