You are once again in a labyrinth. Your mission is to collect all coins and finally move to the exit cell. What is the minimum number of steps needed for this?

Each cell in the labyrinth is one of following:

• #: wall
• .: floor
• A: starting cell
• B: exit cell
• *: coin

At each step, you can move one cell left, right, up or down.

Input

The first input line contains three integers $n$, $m$ and $k$: the height and the width of the labyrinth and the number of coins.

After this, the input describes the labyrinth. There are $n$ lines, each containing $m$ characters.

Output

Output the minimum number of steps needed for collecting the coins and finally moving to the exit cell.

You can assume that it is always possible to complete the mission.

Constraints

• $1 \le n, m \le 100$
• $0 \le k \le 8$

Example

Input:

3 6 3
.AB#.*
.....#
*..#.*

Output:

19