Повторюваний рядок

Обмеження: 2 сек., 256 МіБ

У Керема є рядок \(s\) завдовжки \(n\), що складається з малих букв.

Нехай \(f(s)\) — це таке мінімальне додатне \(k\), що \(s_i=s_{i+k}\) для всіх \(1 \le i \le n-k\).

Аслі хоче переставити літери в рядку \(s\) та отримати рядок \(t\) такий, що \(f(t)\) мінімальне.

Допоможіть їй це зробити.

Вхідні дані

Вхідні дані містять рядок \(s\).

Вихідні дані

Виведіть мінімальне значення \(f(t)\) серед усіх перестановок.

Обмеження

\(1 \le n \le 5 \cdot 10^5\),

\(s\) складається з малих англійських букв.

Приклади