Нельзя сказать, что программисты — рассеянный народ, но многие его отдельные представители страдают этим недугом… Однажды Артемий Сидорович тестировал заготовку своей программы. В частности, она должна была уметь определять день недели по введённой дате. Артемий Сидорович ввёл 11 октября 2003 года и получил в ответ: «Суббота». «Ага!» — обрадовался Артемий Сидорович и стал искать ошибку. Дело в том, что календарь, который висел на стене его кабинета, гласил, что 11 октября — понедельник.

После часа убитого впустую времени Артемий Сидорович поднял голову и увидел на календаре большие цифры: 1999. Выругавшись про себя и пообещав снять старый календарь, Артемий Сидорович взглянул на часы. Часовая стрелка подходила к отметке IIII. Рабочий день постепенно шёл к концу.

— Интересно, — подумал Артемий Сидорович, — ведь я много раз видел, что число 4 записывается римскими цифрами IV. Выходит, что десятичное число неоднозначно представляется в римской записи. Он вновь бросил взгляд на злосчастный календарь и подумал так:

— Пусть числа 1, 5, 10, 50, 100, 500, 1000 обозначаются римскими цифрами I, V, X, L, C, D, M. Тогда число 1999 можно записать как MDCCCCLXXXXVIIII или просто MIM. А может — MCMXCIX. Понятно, что самая короткая запись — MIM, но какая из них — правильная?

Желая устранить эту несправедливость, Артемий Сидорович решил:

— Назовём псевдоримским числом следующую последовательность цифр: A₁A₂…A_n, где:

Тогда число 4 запишется IV, а не IIII (по правилу 2). Число 1999 запишется MCMXCIX. Пусть получается не самый короткий способ записи, но зато, кажется, каждое число записывается единственным образом.

В единственной строке расположено десятичное целое число N, 1 ≤ N ≤ 10²⁰⁰³.

Выведите единственное число K — количество цифр в псевдоримской записи числа N.

1939 = MCMXXXIX