Problem

This year again, the cheese factories in JOI Town have started producing cheese, and a mouse has poked its head out of its nest. JOI Town is divided into a grid of blocks running north, south, east, and west, and each block is either the nest, a cheese factory, an obstacle, or an empty lot. The mouse starts from its nest, visits all the cheese factories, and eats $1$ piece of cheese at each factory.

In this town, there are $N$ cheese factories, and each factory produces only $1$ type of cheese. The hardness of the cheese differs from factory to factory, and there is exactly $1$ cheese factory producing cheese of each hardness from $1$ to $N$.

The initial strength of the mouse is $1$, and each time it eats $1$ piece of cheese, its strength increases by $1$. However, the mouse cannot eat cheese that is harder than its current strength.

The mouse can move to an adjacent block to the north, south, east, or west in $1$ minute, but it cannot enter a block with an obstacle. It can also pass through a cheese factory without eating the cheese. Write a program to find the minimum time required to finish eating all the cheese. Note that the time it takes for the mouse to eat cheese can be ignored.

Input

The input consists of $H+1$ lines. The $1$-st line contains $3$ integers $H$, $W$, and $N$ ($1 \le H \le 1000$, $1 \le W \le 1000$, $1 \le N \le 9$) in this order, separated by spaces. Each line from the $2$-nd line to line $H+1$ contains a string of $W$ characters consisting of S, 1, 2, $\dots$, 9, X, and ., representing the state of each block. If we denote the block that is $i$-th from the north and $j$-th from the west as $(i, j)$ ($1 \le i \le H, 1 \le j \le W$), then the $j$-th character on line $i+1$ is S if block $(i, j)$ is the nest, X if it is an obstacle, . if it is an empty lot, and 1, 2, $\dots$, 9 if it is a factory producing cheese of hardness $1, 2, \dots, 9$, respectively. In the input, there is $1$ of each of the nest and the factories producing cheese of hardness $1, 2, \dots, N$. All other cells are guaranteed to be obstacles or empty lots. The mouse is guaranteed to be able to eat all the cheese.

Output

Output on $1$ line an integer representing the minimum time (in minutes) required to finish eating all the cheese.

Input/Output Examples

Input Example 1

3 3 1
S..
...
..1

Output Example 1

4

Input Example 2

4 5 2
.X..1
....X
.XX.S
.2.X.

Output Example 2

12

Input Example 3

10 10 9
.X...X.S.X
6..5X..X1X
...XXXX..X
X..9X...X.
8.X2X..X3X
...XX.X4..
XX....7X..
X..X..XX..
X...X.XX..
..X.......

Output Example 3

91