描述

在生物遗传学理论中，基因是携带遗传信息的载体，而基因可以用碱基序列的形式来表达。例如，AGTCCGATAGC是属于一种生物A的基因序列，AGTCGATCGC是属于另一种生物B的基因序列。通常情况下，基因序列越相似的两种生物，两者表现出来的生物性状就越接近。

利用这种特性，科学家可以通过比对两种生物的基因序列，来推测两者之间的遗传关系。由于全部生物的基因库非常庞大，手动一个个比对既耗时又容易出错，所以需要一个程序来自动找出两个基因序列之间的最长的公共子序列的长度。注意，子序列的字符不一定在原序列中的位置是连续的。

例如，对于以下两个序列，最长的公共子序列为AGTCGATGC，长度为9。这个子序列是AGTCGATGC，由AGTC-GAT-GC三部分组成。

AGTCCGATAGC
AGTCGATCGC

输入输出格式

输入

两行，每行一个非空字符串，各代表一个基因序列。

输出

输出一个整数，表示两个序列的最长公共子序列的长度。

样例

AGTCCGATAGC
AGTCGATCGC

9