题目描述

给定一个只含小写字母的字符串 $s$，长度记为 $n$。

对 $s$ 的每一个前缀（长度依次为 $1,2,\dots,n$），定义它的「循环节长度」$p$：

• 如果这个前缀可以写成某个长度 $p$ 的串重复 $\dfrac{|前缀|}{p}$ 次（要求 $p$ 能整除前缀长度），那么 $p$ 取最小的这样的值；
• 否则 $p$ 就等于这个前缀的长度。

请你求出这 $n$ 个前缀的 $p$ 之和。

输入格式

一行一个字符串 $s$。

输出格式

一行一个整数，表示所有前缀循环节长度之和。

输入输出样例 #1

输入 #1

abcabcabc

输出 #1

36

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 10^6$。和可能到 $\dfrac{n(n+1)}{2}\approx 5\times 10^{11}$。