Description

求每个字符串的最短循环子串，输出为循环次数。

Format

Input

输入数据为多组数据，读取到“.”字符时结束。每组数据仅有一行，长不会超过1,000,000个字符。

Output

对于每组数据，输出一行，一个整数表示这个字符串的最短循环子串的循环次数。

Sample 1

Input

abcd
aaaa
ababab
.

Output

1
4
3

Limitation

1s, 32MiB for each test case.

Hint

Source

poj2406