Given a map of a dungeon, your task is to take all TWO diamonds in the dungeon.

Find the minimum number of gates you have to open to take all the diamonds.

Note: It can be more than one gate to go into the dungeon from the outside.

You can move up, down, left, right or diagonal

About the map:

• The letter '.' means blank space, you can move on it

• The letter '*' means blockade, you have to go around it

• The letter '#' means there's a gate at that place, you need it opened to go through it

• The letter '$' means the diamond.

Input format:

• First line is two number N and M — the dungeon has the size N*M.

• N lines following, represent the map of the dungeon.

Output format:

• A single integer — the minimum number of gates you have to open.

Example input:

5 9

****#****

..#.#..

****.****

$$$#.#.#$$$

Example output: 4

Thank you guys, hope you have a great standing in the next contest.