题目描述

给定两个字符串序列X和Y，长度都不超过5000，求出两个序列的最长公共子序列长度。注意:子序列不是子串，不要求连续，例如两个字符串cnblogs和belong的公共子序列为blog.可以发现，最长公共子序列是不唯一-的，但是长度一定是唯一的。

输入格式

两行，每行一个只含英文字母的字符串

输出格式

一个数，表示两个字符串的最长公共子串的长度

样例

输入

cnblogs
belong

输出

4