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