URI Online Judge | 2824

Pudim

By Emilio Wuerges, UFFS BR Brazil

Timelimit: 1

The worldly famous website pudim.com.br will soon launch its search engine. The main thing about this search engine is that it will rank articles according to user searches.

It is almost done. The only thing missing is the ranking algorithm.

After a lot of thought, it was decided that articles will be graded using the size of the largest common substring between the search and article strings. In other words, the size of the largest string that can be formed using only characters that are in both the search and article strings, in the same order.

Input

The input consists of two lines, each one with a string. The first line has the search string and the second line has the article. Both strings only have characters from a to z, without spaces.

The size of the strings, be it the search string or the article string, is at most \(5 \times 10^3\) characters.

Output

The output contains only a single line with an integer: the grade for the article.

Input Samples Output Samples

pudim
phudim

5

Pudim
pudim

4

axbxc
zazbzcz

3