Three states are located on a rectangular map of size n * m. From any cell of any state, you can go to any cell of the same state, moving only along its cells horizontally or vertically. The cells of each state are marked with one of the numbers (1, 2 or 3).

There are passable (".") and impassable ("#") cells on the map.

Build roads on the smallest number of passable cells so that you can go from any cell of one state to any cell of another state. You can freely move around the cells of any state. You can only move along the map horizontally or vertically.

Input

First line contains the size of the map n and m (1 ≤ n, m ≤ 1000). Each of the next n lines contains m symbols:

• 1, 2, 3 - cells that belong to the states;
• "." - passable cell, here you can build a road;
• "#" - impassable cell, here you cannot build a road;

Output

Print the smallest number of cells in which roads should be built so that all cells of all states will be connected. If it is impossible to do this, print -1.