Longest Common Subsequence

Ferndale Publishing keeps two transcripts of the same interview, typed by two different people. Editorial wants a similarity score before deciding whether to merge them: the length of the longest stretch of characters that appears in both transcripts in the same order, allowing either typist to have inserted extra characters in between. Order is the whole point — two transcripts holding the same characters shuffled around are not similar.

Task: Print the length of the longest run of characters that both lines contain in the same left-to-right order.

Input

Two lines. Each holds between 1 and 500 lowercase letters, with no spaces. The two lines may be of different lengths.

Output

One line holding a single integer: how many characters that shared run holds. The chosen characters need not sit next to each other in either line, but they must appear in the same relative order in both, and each character of a line can be used at most once. Print 0 when the two lines share nothing.

Example:

Input:
abcde
ace

Output:
3