Repeating String

Limits: 2 sec., 256 MiB

Kerem has a string \(S\) of length \(n\) consisting of lowercase letters.

Let \(f(S)\) be such minimum positive \(k\) that \(S_i=S_{i+k}\) for all \(1 \le i \le n-k\). Asli wants to reorder letters in string \(S\) to get string \(T\) such that \(f(T)\) is minimal. Help her to do that.

Input

The first line contains string \(S\).

Output

Print the minimum value of \(f(T)\) among all reorderings.

Constraints

\(1 \le n \le 5\cdot10^5\),

\(S\) consists of lowercase English letters.

Samples