Description

The warrior will go through a labyrinth to help his princess. There are different kind of room in the labyrinth. The room may be block or empty. In other case, there are small or large monster in the room. At first, the warrior can only defeat the small monster but not large. After kill a certain number of small monsters, the capability of warrior will upgrade to defeat large monster. The hero can move up, down, left or right. His objective is to go through the labyrinth quickly although some monster should be killed. Can you find the best path when the map of labyrinth is given? Of course, the dead monster can't revive.

Input

The first line of each case are the width and height of maze m,n (m,n <=8), and the integer k that is the number of monster should be killed to upgrade. At the next m lines, a string with length n is given to describle the labyrinth. In each string, a letter '.' means empty room, letter '#' means block room, the lowercase 'o' means small monster and uppercase 'O' means large monster. The entey of maze is left-top, and the exit is right-bottom.

Output

Output the best step in one line for each case. If there is no route, output -1.

Sample Input

4 4 3 o... .... o.OO o#O.

Sample Output

9

Source

The 2007 ACM-ICPC JiLin Provincial Internet Contest