После недавнего конца света Азамат, наконец, выучил алгоритм нахождения наибольшей общей подпоследовательности (LCS - longest common subsequence), и ему сразу стало интересно: как будет работать алгоритм, если слова будут круглыми?

В круглых словах не имеет значения с какого символа они начинаются и в каком направлении читаются. Например, слово algorithm можно прочитать как rithmalgo и как oglamhtir.

Если для слов algorithm и grammar в обычном представлении длина наибольшей общей подпоследовательности равна 3 (слово grm), то для круглого варианта этих же слов длина наибольшей общей подпоследовательности равна 4 (слово grma).

Азамат быстро убедился, что известный алгоритм не может получить правильный ответ для круглых слов. Напишите программу, которая сделает это.

Входные данные

В двух строках задается по одному слову. Слова не пустые и длина каждого символа не более 2000 символов.

Выходные данные

Выведите одно целое число - длину наибольшей общей подпоследовательности заданных круглых слов.