Задача №112838. Числа
На доске записано число 1. Каждую секунду Петя может провести над числом одну из двух операций: либо прибавить к числу 1, либо произвольным образом переставить цифры числа (но так, чтобы на первом месте оказался не ноль). После этого Петя вытирает с доски старое число и записывает вместо него получившееся.
Напишите программу, которая для заданного натурального числа определяет, за какое наименьшее число операций Петя может, начав с единицы, дойти до этого числа.
Первая строка входного файла содержит число T (1 ≤ T < 10 4 ) , которое задает количество чисел во входном файле, для которых требуется найти ответ. В последующих T строках задано по одному натуральному числу N i , 2 ≤ N i < 10 9 , 1 ≤ i ≤ T . Известно, что среди чисел N i , 1 ≤ i ≤ T , нет одинаковых.
Выходной файл должен содержать T чисел по одному в строке — в i -й строке должно быть записано наименьшее количество секунд, которое понадобится истратить Пете, чтобы, начав с единицы, записать на доске соответствующее число N i .
Набор тестов состоит из 4 блоков, для которых дополнительно выполняются такие условия:
- 25 баллов: 2 ≤ N i < 100 для всех i .
- 25 баллов: T = 1;100 ≤ N 1 < 10 4 .
- 15 баллов: T > 1;100 ≤ N i < 10 4 для всех i .
- 35 баллов: 10 4 ≤ N < 10 9 для всех i .
3 2 955 21
1 48 12