Задачи
Числовые операции
Числовые операции
На доске записано число 1. Каждую секунду Петя может провести над числом одну из двух операций: либо прибавить к числу 1, либо произвольным образом переставить цифры числа (но так, чтобы на первом месте оказался не ноль). После этого Петя вытирает с доски старое число и записывает вместо него получившееся.
\textbf{Задание}
Напишите программу, которая для заданного натурального числа определяет, за какое наименьшее число операций Петя может, начав с единицы, дойти до этого числа.
\InputFile
Первая строка входного файла содержит число \textit{\textbf{T}}\textbf{ (1 ≤ }\textit{\textbf{T }}\textbf{< 10^4)}, которое задает количество чисел во входном файле, для которых требуется найти ответ. В последующих \textit{T} строках задано по одному натуральному числу \textit{\textbf{N_i}},\textbf{2 ≤ }\textit{\textbf{N_\{i \}}}\textbf{< 10^9, 1 ≤ }\textit{\textbf{i }}\textbf{≤ }\textit{\textbf{T}}\textbf{.} Известно, что среди чисел\textbf{ }\textit{\textbf{N_i}}\textbf{, 1 ≤ }\textit{\textbf{i }}\textbf{≤ }\textit{\textbf{T}}\textbf{,} нет одинаковых.
\OutputFile
Выходной файл должен содержать \textit{\textbf{T}} чисел по одному в строке --- в \textit{\textbf{i}}\textbf{-й} строке должно быть записано наименьшее количество секунд, которое понадобится истратить Пете, чтобы, начав с единицы, записать на доске соответствующее число \textit{\textbf{N_i}}.
\Scoring
Набор тестов состоит из 4 блоков, для которых дополнительно выполняются такие условия:
\begin{enumerate}
\item 25 баллов: 2 ≤ \textit{N_\{i \}} < 100 для всех \textit{i}.
\item 25 баллов: T = 1;100 ≤ \textit{N}_1\textit{ }< 10^4.
\item 15 баллов: T > 1; 100 ≤ \textit{N_i} < 10^4 для всех \textit{i.}
\item 35 баллов: 10^4 ≤ \textit{N }< 10^9 для всех \textit{i.}
\end{enumerate}
Входные данные #1
3 2 955 21
Выходные данные #1
1 48 12