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

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