Period of the row

A string (S) is said to have a period (T) if:

[ S = T^n ]

for some integer (n).

Given a string (S), your task is to determine the smallest possible length of (T) such that (S = T^n) for some integer (n).

Input

The input consists of a single string (S), with a length ranging from (1) to (10^6) characters.

Output

Output a single integer representing the length of (T).

Examples