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