Доктор Мориарти посылает сообщение Шерлоку Холмсу. В его распоряжении имеется строка s.
Строка p называется подстрокой строки s, если ее можно прочитать, начиная с некоторой позиции в строке s. Например, у строки «aba» есть шесть подстрок: «a», «b», «a», «ab», «ba», «aba».
Доктор Мориарти планирует вырезать из строки s некоторую подстроку, назовем ее t. Потом он должен ноль или более раз изменить вырезанную подстроку t. В результате должна получиться фиксированная строка u (именно ее нужно отправить Шерлоку Холмсу). За одно изменение считается одно из следующих действий:
- Вставить одну букву с любого конца строки.
- Удалить одну букву с любого конца строки.
- Заменить одну любую букву на любую другую.
Мориарти очень умен, поэтому после выбора какой-то подстроки t он всегда делает минимальное количество изменений, чтобы получить u.
Помогите Мориарти выбрать среди всех подстрок строки s наилучшую подстроку t такую, что количество сделанных им изменений для получения из нее строки u будет минимально.
Выходные данные
Выведите единственное число — минимальное количество изменений, которые придется выполнить доктору Мориарти с подстрокой, которую Вы выберете.
Примечание
В первом примере Мориарти может взять любую подстроку длины 3, и она будет равна требуемому сообщению u, так что никаких изменений Мориарти делать не придется.
Во втором примере надо взять подстроку, состоящую из символов со второго по четвертый («bca») или с пятого по шестой («bc»). Тогда придется сделать всего одно изменение: заменить или добавить последний символ.
В третьем примере исходная строка s не содержит ни одного символа, который должен быть в сообщении, так что, какую подстроку не возьми, придется сделать как минимум 7 изменений, чтобы получить требуемое сообщение.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
aaaaa
aaa
|
0
|
|
2
|
abcabc
bcd
|
1
|
|
3
|
abcdef
klmnopq
|
7
|