Numerical Operations

On the board, the number 1 is initially written. Every second, Petryk can choose to perform one of two operations on this number: either add 1 to it, or rearrange its digits in any order (ensuring that the first digit is not zero). After performing an operation, Petryk erases the old number and writes the new one on the board.

**Task**

Write a program to determine the minimum number of operations Petryk needs to reach a given natural number, starting from one.

**Input**

The first line of the input contains the integer (T) ((1 $\le$ T < 10^4)), which indicates the number of target numbers for which you need to find the answer. The next (T) lines each contain one natural number (N_i) ((2 $\le$ N_i < 10^9, 1 $\le$ i $\le$ T)). It is guaranteed that all numbers (N_i) are distinct.

**Output**

The output should consist of (T) lines, each containing a single integer. The (i)-th line should display the minimum number of seconds Petryk needs to write the corresponding number (N_i) on the board, starting from one.

**Scoring**

The test set is divided into 4 blocks, with the following additional conditions:

1. 25 points: (2 $\le$ N_i < 100) for all (i).

2. 25 points: (T = 1); (100 $\le$ N_1 < 10^4).

3. 15 points: (T > 1); (100 $\le$ N_i < 10^4) for all (i).

4. 35 points: (10^4 $\le$ N_i < 10^9) for all (i).

Examples