eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 0.2 seconds
Memory limit 64 MiB

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

Задание

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

Input data

Первая строка входного файла содержит число T (1 ≤ T < 10^4), которое задает количество чисел во входном файле, для которых требуется найти ответ. В последующих T строках задано по одному натуральному числу N_i,2 ≤ N_{i }< 10^9, 1 ≤ i T. Известно, что среди чиселN_i, 1 ≤ i T, нет одинаковых.

Output data

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

Examples

Input example #1
3
2
955
21
Output example #1
1
48
12

Scoring

Набор тестов состоит из 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.

Author Данило Мисак
Source XXVII Всеукраинская ученическая олимпиада по информатике (2014) Днепропетровск