Задача №1729. New RLE

Программист и математик Кумар Харикришнин разработал новый метод сжатия данных — ACM (Advanced Compression Method) — основанный на его гениальных идеях.

Первая часть ACM будет модификацией широко известного метода RLE и будет называться “New RLE”. Алгоритм должен заменять повторяющиеся подстроки исходной строки на одно вхождение подстроки с приписанным к нему количеством повторений. Если некоторая подстрока не должна повторяться, к ней нужно приписать единицу.

Ваша программа должна находить кратчайшее представление данной строки в данном формате.

Входные данные

Входной файл содержит непустую строку, длиной не более 1000 символов, которая должна быть сжата. Она может содержать ПРОБЕЛЫ, но не может содержать цифр.

Выходные данные

Выведите сжатую строку минимальной длины. В выходном файле не должно быть незначащих пробелов в начале и конце строки. Если таких строк несколько — выведите любую из них.

Примеры тестов

Входные данные

aaaaaaaaaa

Выходные данные

a10

Входные данные

a c c c

Выходные данные

a1 c3

Входные данные

abc

Выходные данные

abc1

Сдать: для сдачи задач необходимо войти в систему