Программист и математик Кумар Харикришна разработал новый метод сжатия данных --- ACM (Advanced Compression Method) --- который воплотил в себе все его блестящие идеи. Первой компонентой ACM является модификация известного RLE алгоритма, известного как улучшенный RLE. Так как Кумару следует выполнить более сложные задачи (написать Улучшенного Хемминга или Улучшенного Лемпеля-Зива), он просит Вас реализовать эту простую, но очень важную часть системы. Алгоритм должен заменить повторяющиеся подстроки входной строки одной подстрокой, за которой следует количество ее повторений. Если некоторая подстрока не повторяется, то после нее следует записать \textbf{1}. Ваша программа должна найти кратчайшее возможное сжатие заданной строки. \InputFile Единственная входная строка, которая должна быть сжата. Она может содержать пробелы, но не должна содержать цифры, чтобы в изобретенном Кумаром методе сжатия процесс декодирования строки происходил однозначно. \OutputFile Вывести кратчайшее по длине сжатие входной строки. Не следует выводить лишних пробелов перед строкой или после нее.