На дошці записано число 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}