Задачі
Числові операції
Числові операції
На дошці записано число 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{T} чисел по одному в рядку --- в \textit{i}-му рядку має бути записано найменшу кількість секунд, які знадобиться витратити Петрику, щоб, почавши з одиниці, записати на дошці відповідне число \textit{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