eolymp
Задачи

Числовые операции

Числовые операции

На доске записано число 1. Каждую секунду Петя может провести над числом одну из двух операций: либо прибавить к числу 1, либо произвольным образом переставить цифры числа (но так, чтобы на первом месте оказался не ноль). После этого Петя вытирает с доски старое число и записывает вместо него получившееся.

Задание

Напишите программу, которая для заданного натурального числа определяет, за какое наименьшее число операций Петя может, начав с единицы, дойти до этого числа.

Входные данные

Первая строка входного файла содержит число T (1 ≤ T < 104), которое задает количество чисел во входном файле, для которых требуется найти ответ. В последующих T строках задано по одному натуральному числу Ni,2 ≤ Ni < 109, 1 ≤ iT. Известно, что среди чиселNi, 1 ≤ i T, нет одинаковых.

Выходные данные

Выходной файл должен содержать T чисел по одному в строке — в i строке должно быть записано наименьшее количество секунд, которое понадобится истратить Пете, чтобы, начав с единицы, записать на доске соответствующее число Ni.

Оценивание

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

  1. 25 баллов: 2 ≤ Ni < 100 для всех i.
  2. 25 баллов: T = 1;100 ≤ N1< 104.
  3. 15 баллов: T > 1; 100 ≤ Ni < 104 для всех i.
  4. 35 баллов: 104N < 109 для всех i.
Лимит времени 0.2 секунд
Лимит использования памяти 64 MiB
Входные данные #1
3
2
955
21
Выходные данные #1
1
48
12
Автор Данило Мисак
Источник XXVII Всеукраинская ученическая олимпиада по информатике (2014) Днепропетровск