A. Двоично-десятичные
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем число двоично-десятичным, если оно целое, положительное, и все его цифры в десятичной системе счисления равны либо $$$0$$$, либо $$$1$$$. Например, $$$1\,010\,111$$$ — двоично-десятичное число, а $$$10\,201$$$ и $$$787\,788$$$ — нет.

Дано число $$$n$$$, вас просят представить $$$n$$$ как сумму нескольких (не обязательно различных) двоично-десятичных чисел. Найдите минимальное необходимое для этого количество двоично-десятичных чисел.

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Каждый набор входных данных задан на отдельной строке и содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^9$$$) — число, которое нужно представить в виде суммы.

Выходные данные

Для каждого набора входных данных выведите минимальное необходимое количество двоично-десятичных чисел для представления числа $$$n$$$ в виде суммы.

Пример
Входные данные
3
121
5
1000000000
Выходные данные
2
5
1
Примечание

В первом наборе входных данных число $$$121$$$ можно представить, например, как $$$121 = 110 + 11$$$ или $$$121 = 111 + 10$$$.

Во втором наборе входных данных число $$$5$$$ можно представить как $$$5 = 1 + 1 + 1 + 1 + 1$$$.

В третьем наборе входных данных число $$$1\,000\,000\,000$$$ само является двоично-десятичным, поэтому ответ равен $$$1$$$.