На свой день рождения Уэнсдей получила длинную строку $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$.