Максимальная общая подстрока#4845

Максимальная общая подстрока

3 секунды
256 мегабайт
Easy

Дана строка A = a_1a_2...a_n и строка B = b_1b_2...b_m.

Нужно узнать длину их максимальной общей подстроки.

Input

В первых двух строках записаны строки A и B, состоящие из строчных латинских букв. Эти строки непустые и имеют длину не более 30000 символов.

Output

В выходной файл выведите длину их максимальной общей подстроки.

Examples

Example 1

Loading
Loading