Прошло уже немало лет с тех пор, как Лич Сандро ушёл на заслуженный отдых. Иногда по вечерам, когда ему становится совсем тоскливо, он берёт в руки книгу, которую ему подарили воспитанники-маги по случаю выхода на пенсию.

Вот и сейчас великий маг взял с полки книгу и углубился в чтение. В одной из глав рассказывалось про знаменитое открытие Сандро — много лет назад он придумал универсальное заклинание. Оказалось, что любая его подстрока (последовательность подряд идущих букв) тоже является заклинанием, а сила любого заклинания равна количеству раз, которое это заклинание встречается в универсальном (например, строка «ue» встречается в строке «queue» дважды, а строка «aba» в строке «abababa» — трижды).

Сейчас у Сандро много свободного времени, и он решил найти самое сильное заклинание. Помогите ему в этом.

Единственная строка содержит универсальное заклинание, которое открыл Сандро. Заклинание — непустая строка из строчных латинских букв длиной не более 50.

Выведите любое из заклинаний, обладающих, по мнению Сандро, наибольшей силой.