lcs

A subsequence is a sequence derived from an another original sequence by deleting some elements while leaving the order unchanged.

Given 2 strings, find the length of the longest common subsequence between them. There will be no spaces in the strings and it would be less than 1000 characters long.

Input

2 strings, one on each line

Output

A single integer indicating the length of the longest common subsequence.

Sample Input 1

happy
apple

Sample Output

3 [app is common]

Sample Input 2

Ranald
Iran

Sample Output 2

2 [an is common, R and r are not considered the same]