Problem description

Po kursie z algorytmów tekstowych, Jasio nadal ma problem z odróżnieniem podciągu od podsłowa. W związku z tym, prowadzący postanowił przygotować dla niego specjalne zadanie. Dla danych słów A, B oraz S, Jasio ma obliczyć długość najdłuższego wspólnego podciągu słów A i B, takiego że zawiera S jako podsłowo.

W ramach przypomnienia: podciąg to słowo, powstałe poprzez usunięcie pewnych (być może żadnych) liter ze słowa, a następnie odczytanie pozostałych liter od lewej do prawej. Natomiast podsłowo to słowo, powstałe poprzez usunięcie pewnych (być może żadnych) liter z początku oraz końca słowa, a następnie odczytanie pozostałych liter od lewej do prawej. Na przykład dla słowa alekoala, jednym z jego podciągów jest eol, a jednym z jego podsłów jest lek.

Wejście

W pierwszych trzech wierszach wejścia znajdują się trzy słowa (składające się z małych liter alfabetu angielskiego) A, B oraz S.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć długość najdłuższego wspólnego podciągu słów A i B, takiego że zawiera S jako podsłowo. Jeżeli taki podciąg nie istnieje, Twój program powinien wypisać 0.

Ograniczenia

Długość każdego z napisów na wejściu nie przekracza 5000 znaków.

Przykład

alekoala
alxekkoxa
lek

6