Некоторые вирусы реплицируются путем замены фрагмента ДНК в живой клетке фрагментом ДНК, который вирус несет с собой. Это заставляет клетку создавать вирусы, идентичные оригинальной, зараженной клеткой. Группа биологов заинтересована в том, чтобы узнать, сколько ДНК вносит вирус в геном хозяина. Чтобы узнать об этом, они упорядочили полный геном здоровой клетки, а также идентичную клетку, инфицированную вирусом.

Геном оказался довольно большим, поэтому теперь им нужна Ваша помощь на этапе обработки данных. Имея последовательность ДНК до и после вирусной инфекции, определите длину самой маленькой одиночной последовательной части ДНК, которая может быть вставлена в первую последовательность, чтобы превратить ее во вторую. Один последовательный фрагмент ДНК также мог быть удален из того же положения в последовательности, что и ДНК. Небольшие изменения в ДНК могут иметь большие эффекты, поэтому вирус может вставить только несколько букв или даже ничего.

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

Состоит из двух строк, содержащих последовательность ДНК до и после вирусной инфекции, соответственно. Последовательность ДНК задается как строка, содержащая от 1 до 105 букв верхнего регистра из алфавита {A, G, C, T}.

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

Выведите одно целое число - минимальную длину ДНК, вставленную вирусом.