Minimum Stamp Length

You are given a string S which represents the sequence of letters printed on a paper. You plan to produce this string by repeatedly stamping a carved stamp. Each stamping operation prints all the characters on the stamp (i.e. a contiguous block of letters) onto the paper. A stamp may be used multiple times and may overlap with previous stamps; printing the same letter at the same position repeatedly is allowed. However, if two stampings overlap at some position, the letter printed from both applications must be identical (— you cannot print different letters on the same position, because once printed, letters cannot be removed).

For example, if the stamp is aba, you can obtain the printed string ababa by stamping at positions 1 and 3, since the overlapping position (position 3) gets the letter a from both stampings. On the other hand, you cannot form abcba with the stamp aba because the overlapping letters would conflict.

Your task is to choose a stamp (i.e. determine its string) with as few characters as possible such that it is possible to cover the whole printed string S by a sequence of stampings. Each stamping must print the entire stamp and must lie completely within S (that is, if the stamp has length L, it can only be stamped starting at positions 1 to |S| - L + 1).

Hint: Let s = S[1..L] be the stamp you choose. When stamping, the stamps may overlap. If you choose to stamp in a way that maximizes the overlap, suppose you stamp first at position 1 and then at position 1 + (L - f) where f is the length of the longest proper prefix of s that is also a suffix of s. Then the stamp effectively contributes L - f new characters each time after the first stamp. In order to cover S, it must be that for every position i in S (after the first stamp) the following holds:

\( S[i] = S[i - (L - f)] \)

Your job is to find the minimum possible stamp length L such that if you let s = S[1..L] and f be the length of its longest border (i.e. proper prefix which is also a suffix), then for every position i from L+1 to |S| the equality S[i] = S[i - (L - f)] holds. Note that stamping positions can be chosen arbitrarily as long as the entire string S is covered and the above overlapping condition is satisfied.

inputFormat

The input consists of a single line containing the string S (1≤|S|≤10⁵), composed of lowercase English letters.

outputFormat

Output a single integer, which is the minimum length of the stamp that can be used to produce S via a sequence of stampings.

sample

ababa

3