[POI2005]Sza-Template

Byteasar 想在墙上喷涂一个很长的字符串。为此，他从目标字符串的开头截取一段字符，制作成模板，并将该模板反复喷涂在适当的位置，最终得到完整的目标字符串。

同一个位置可以被喷涂多次，但每次喷涂在该位置上的字符必须相同。由于制作模板十分费力，Byteasar 希望模板尽可能短。

请你求出能够生成目标字符串的最短模板长度。

例如，对于字符串 ababbababbabababbabababbababbaba，可以取其前 $8$ 个字符 ababbaba 作为模板，通过在适当的位置重复喷涂得到整个字符串。

输入格式

输入一行一个仅由小写英文字母组成的字符串。

输出格式

输出一个整数，表示最短模板的长度。

样例输入

ababbababbabababbabababbababbaba

样例输出

8

样例解释

最短模板为目标字符串的前 $8$ 个字符 ababbaba。

数据范围

• 设输入字符串的长度为 $n$，则 $1\le n\le 5\times 10^5$。

来源与许可

本题为 POI 2005 试题「Sza-Template」，题面与测试数据整理自 BZOJ。

样例 1

输入

ababbababbabababbabababbababbaba

输出

8