Подарок Уэнсдей
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На свой день рождения Уэнсдей получила длинную строку $$$s$$$. Как известно, Уэнсдей ненавидит подарки, не связанные с пытками, поэтому увидев такой ужасный подарок, она сразу же захотела покрамсать его на мелкие части. Однако перед тем как приступить к своей затее, она заметила, что строку $$$s$$$ можно разрезать так, что в результате получится собрать две проклятые строки $$$t_1$$$ и $$$t_2$$$, которые очень нужны ей для пыток.

Уэнсдей может разрезать строку $$$s$$$ несколько раз в любом месте. После этого она возьмет изначально пустые строки $$$a$$$ и $$$b$$$ и рассмотрит получившиеся после разрезания части $$$s$$$ слева направо: каждую часть она припишет либо в конец строки $$$a$$$, либо в конец строки $$$b$$$. В конце должно получиться: $$$$$$ a = t_1,\qquad b = t_2,\qquad \lvert a\rvert + \lvert b\rvert = \lvert s\rvert. $$$$$$

Уэнсдей не терпится заполучить проклятые строки и приступить к пыткам, поэтому она просит Вас определить минимальное количество разрезов строки $$$s$$$, достаточное, чтобы описанным способом можно было получить строки $$$t_1$$$ и $$$t_2$$$.

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

Первая строка входных данных содержит строку $$$s$$$ ($$$3 \le |s| \le 10^4$$$).

В следующих двух строках входных данных содержатся непустые строки $$$t_1$$$ и $$$t_2$$$ соответственно.

Гарантируется, что $$$|t_1|$$$ + $$$|t_2|$$$ = $$$|s|$$$. Все строки состоят из строчных латинских букв.

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

Выведите единственное число — минимальное количество разрезов строки $$$s$$$, чтобы можно было получить строки $$$t_1$$$ и $$$t_2$$$ описанным выше способом. Гарантируется, что ответ всегда существует.

Примеры

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

    wedneseniddaywednesdayenid

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

    2

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

    shadowednesdaywwednesdayshadow

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

    2

Примечание

Пример 1: Можно разрезать строку следующим образом: wednes | enid | day Тогда первая и последняя часть образуют строку $$$t_1$$$, а средняя — строку $$$t_2$$$.

Пример 2: Можно разрезать строку следующим образом: shado | wednesday | w Тогда первая и последняя часть образуют строку $$$t_2$$$, а средняя — строку $$$t_1$$$.