Числові операції

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

Приклади

Оцінювання

Набір тестів складається з 4 блоків, для яких додатково виконуються такі умови:

1. 25 балів: 2 ≤ N_{i } < 100 для всіх i.

2. 25 балів: T = 1;100 ≤ N_1 < 10^4.

3. 15 балів: T > 1; 100 ≤ N_i < 10^4 для всіх i.

4. 35 балів: 10^4 ≤ N < 10^9 для всіх i.