Назовем число двоично-десятичным, если оно целое, положительное, и все его цифры в десятичной системе счисления равны либо \(0\), либо \(1\). Например, \(1\,010\,111\) — двоично-десятичное число, а \(10\,201\) и \(787\,788\) — нет.
Дано число \(n\), вас просят представить \(n\) как сумму нескольких (не обязательно различных) двоично-десятичных чисел. Найдите минимальное необходимое для этого количество двоично-десятичных чисел.
Выходные данные
Для каждого набора входных данных выведите минимальное необходимое количество двоично-десятичных чисел для представления числа \(n\) в виде суммы.
Примечание
В первом наборе входных данных число \(121\) можно представить, например, как \(121 = 110 + 11\) или \(121 = 111 + 10\).
Во втором наборе входных данных число \(5\) можно представить как \(5 = 1 + 1 + 1 + 1 + 1\).
В третьем наборе входных данных число \(1\,000\,000\,000\) само является двоично-десятичным, поэтому ответ равен \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
121
5
1000000000
|
2
5
1
|