Числовые операции
Числовые операции
На доске записано число 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.
Пример
3 2 955 21
1 48 12
Оценивание
Набор тестов состоит из 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.