Задача B. Пронумерованный борт

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:64 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Генералиссимус Флатландских вооруженных сил проводил совещание со своим заместителем. Основным вопросом обсуждения стало состояние непобедимой танковой армады наиболее вероятного противника - Берляндии. Перед вами отрывок из стенограммы заседания.

- Итак, коллеги, резюмируем. Мы не знаем, сколько танков у Берляндии. Даже примерно. Наш разведчик сообщил, что ему удалось тайком сфотографировать один из танков с бортовым номером, давайте думать, какую информацию мы сможем из этого извлечь.

- Шеф, нам известна система нумерации танков берляндских вооруженных сил. Бортовой номер состоит из трех частей. Первое число - порядковый номер танкового батальона, второе число - порядковый номер роты в батальоне и третье число - порядковый номер танка в роте. Все числа могут иметь ведущие нули. Например, если в роте 150 танков, третье число на борту будет написано так: (001, 002, ..., 010, ..., 100, ..., 150). Лишних ведущих нулей они не пишут, поэтому, если, например, третье число на танке 04, значит в каждой роте не меньше десяти, и не более 99 танков.

- Значит, если номер танка 12-3-04, то у противника от 12 до 99 батальонов, в каждом из них от 3 до 9 рот (нам ведь точно известно, что Берляндцы зациклены на порядке, и у них всё в армии одинаковое), а в каждой роте от 10 до 99 танков. Где мой калькулятор? Получается, что по этому номеру мы определим, что в Берляндии от 360 до 88209 танков.

Бесшумно появившейся адъютант положил перед Генералиссимусом запечатанный конверт и так же тихо удалился.

- Вот и долгожданная фотография! Посмотрим...

Очень долгая пауза.

- Шеф, у нас две проблемы. Первая - берляндцы не используют разделители в бортовых номерах. Действительно - зачем им это? Они и так знают, сколько у них батальонов, рот и танков в каждой роте. Вторая - судя по длине номера, танков у них очень много.

- Что верно, то верно... Передайте номер нашему программисту, пусть найдет наименьшее возможное количество танков хитрых берляндцев!

Формат входных данных

Единственная строка входного файла содержит натуральное число n - бортовой номер танка. Гарантируется наличие в номере не менее трех цифр, отличных от нуля.

Формат выходных данных

Выведите одно натуральное число - минимальное достоверное количество танков в Берляндии.

Ограничения

111 ≤ n ≤ 1015

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

В первом примере n = 123. Разделители можно расставить единственным образом: 1-2-3. В Берляндии не менее одного батальона, не менее двух рот в каждом батальоне, не менее трех танков в каждой роте. Итого у противника не менее 6 танков.

Во втором примере n = 1024. Есть три возможности расставить два разделителя.

Первая: 10-2-4. В Берляндии не менее десяти батальонов, не менее двух рот в каждом, не менее четырёх танков в каждой. Итого у противника не менее 80 танков.

Вторая: 1-02-4. В Берляндии не менее одного батальона, не менее десяти рот в каждом, не менее четырёх танков в каждой. Итого у противника не менее 40 танков.

Третья расстановка 1-0-24 невозможна - нумерация в армии Берляндии начинается с 1, поэтому рота не может иметь номер 0 (а также 00, 000 и так далее). В итоге можно с уверенностью утверждать, что независимо от расстановки разделителей, хотя бы 40 танков у противника точно имеется.

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

Стандартный вход Стандартный выход
1
123
6
2
1024
40

0.109s 0.026s 15