Hack around the Lock

Time limit5sMemory limit256 MB

Summary

Starting from a given K-digit lock setting, find the minimum number of single-wheel rotations needed to visit every other K-digit setting at least once.

Level: Medium7 of 10
Topics: Graph, Math, Greedy, Dynamic programming
Solved: No attempts yet

Problem

You have a suitcase with a numeric combination lock made of $K$ wheels. Each wheel shows one digit from $0$ to $9$ , so every setting of the lock is a $K$ -digit number (leading zeros are kept and still count as digits). Exactly one setting opens the lock.

You chose the secret setting with a careful random generator, and then you forgot it. Rather than spin the wheels at random, you decide to try every possible setting in turn; because you are unlucky, the correct setting is always the very last one you reach.

In one step you rotate a single wheel by one position, changing that wheel's digit by exactly $1$ . A wheel cannot jump directly between $0$ and $9$ : moving from $0$ to $9$ (or back) takes $9$ steps. After each step you may test the current setting. The initial setting is known to be wrong, so you start from it.

Given the initial setting, determine the minimum number of steps needed so that, starting from it, every other $K$ -digit setting is reached (tried) at least once.

Input

The input contains several test instances. Each instance is a single line holding one decimal number $N$ , the initial setting. $N$ may contain leading zeros, which are part of its digit count $K$ (with $1 \le K \le 7$ ); for example, 007 is a $3$ -digit setting. The list of instances ends with a line containing -1.

Output

For each instance, print one line containing the minimum number of steps $S$ : the fewest single-wheel rotations, starting from the given setting, after which every other $K$ -digit setting has been tried at least once.

Examples4

Example 1
Input
```
5
00
-1
```
Expected output
```
13
99
```
Example 2
Input
```
0
9
-1
```
Expected output
```
9
9
```
Example 3
Input
```
007
-1
```
Expected output
```
999
```
Example 4
Input
```
55
10
99
42
-1
```
Expected output
```
99
99
99
99
```