题目描述

希腊有一个著名的历史学家,他为了专心写一本史学巨著,而把自己关在一个高塔之 上。有一天,他目睹了一场凶杀案的发生,但事后,他惊讶地发现所有围观人的证词都不一 样,甚至有的完全相反。于是,他放弃了继续写作的念头。他说:"人们连发生在眼前的事 实都分辨不清,我又怎么知道我写的历史是真是假呢?"

虽然历史的真假我们很难辨别,但文章是否抄袭,我们还是可以用所谓的$\red{LCS}$算法解 决的。

给出两个字符串$\red{S_1,}$和$\red{S_2,}$我们现在希望了解两个字符串之间的"相似度"。这个相似， 度是这样定义的:找出第三个字符串$\red{S_3,}$组成$\red{S_3}$的元素也出现在$\red{S_1}$和$\red{S_2}$中,而且这些元 素必须是以相同的顺序出现,但不必要是连续的。能找到的$\red{S_3}$越长则$\red{S_1,}$和$\red{S_2}$就越相似。 相似度即是这个$\red{S_3}$的长度。例如,当$\red{S_1=}$"$\red{abede}$",$\red{S_2 = }$"$\red{dabfda}$",$\red{S_3}$就是"$\red{abd}$",$\red{S_1}$和$\red{S_2}$ 的相似度就是$\red{3}$。

输入格式

第一行为一个整数,表示第一个字符串的长度。

第二行为第一个字符串。

第三行为一个整数,表示第二个字符串的长度。

第二行为第二个字符串。

输出格式

一个整数,即两个字符串的相似度。

样例

输入样例

5
abccb
5
acabc

输出样例

3