Template

Byteasar wants to paint a rather long pattern on the wall of his house. To do this he first prepares a suitable template with some letters cut out of it. He paints the pattern by placing the template at a chosen spot on the wall and painting over it: this way he "prints" all the letters on the template at once (it is not possible to print only some of them). A wall cell may be painted several times by different placements of the template, so the template may be stamped at many overlapping positions. The letters on the template are adjacent (there are no gaps between them).

Of course he could make a single template holding the whole pattern, but Byteasar wants to keep the cost down, so he wants the template to be as short as possible.

Write a program that:

• reads the pattern Byteasar wants to paint on his wall from standard input,
• determines the minimal length of a template needed to produce it,
• writes the result to standard output.

Formally, given a string $S$, find the smallest length $|T|$ of a string $T$ such that copies of $T$ can be stamped at several positions of $S$ to reproduce $S$ exactly, where:

• every stamp lies entirely within $S$ and its letters match the corresponding letters of $S$ (so every stamped position is an occurrence of $T$ in $S$), and
• the stamps may overlap, but together they must cover every position of $S$.

The first and only line of standard input contains one word: the pattern Byteasar wants painted on his wall. It consists only of lower-case letters of the English alphabet, and its length is between 1 and 500,000 inclusive.

The first and only line of standard output should contain a single integer: the minimal number of letters in the template (its minimal length).