Zvonimir

Goran likes to sing. His favourite song is Kletva kralja Zvonimira, and because he is not sure that he remembers the whole text, he decides to type it into his computer. The text is a string $X$ of lowercase English letters.

Goran has only two operations, and each one counts as a single operation.

1. Type the next single letter of the text.
2. Take one contiguous part of the text he has typed so far, copy it, and append that copy to the end of the text. The chosen part may have any length and may start at any position.

The part copied by the second operation must be contained in full in the text as it stands right before that operation. Letters that appear while the copy is being appended cannot be part of what is copied.

Find the smallest number of operations that produces the whole string $X$.

The first and only line contains the string $X$ that Goran wants to type. It consists of lowercase English letters and its length satisfies $1 \le |X| \le 200\,000$.

Print on the first and only line the smallest number of operations $S$ that Goran needs to type all of $X$.

For $X$ equal to judinisinovi, $11$ operations are enough: j, u, d, i, n, i, s, in, o, v, i. The eighth operation copies the in that was typed earlier.