Description

给你字符串 $s$ 和 $t$。找到一个最长的字符串，它同时是 $s$ 和 $t$ 的子串。

Input

输入格式如下：

$s\\t$

$s$ 和 $t$ 是由小写英文字母组成的字符串。

$1≤∣s∣,∣t∣≤3000$。 绝对值符号代表长度。

Output

输出最长的字符串长度，它是 $s$ 和 $t$ 的子序列。

Samples

axyb
abyxb

axb

输出axb和ayb都是可以的。

aa
xayaz

aa

a
z

答案为一个空串。

abracadabra
avadakedavra

aaadara