Manhattan Wiring

You are given a rectangular grid of $n \times m$ cells. Exactly two cells are marked "2" and exactly two other cells are marked "3"; some cells are obstacles.

Connect the two "2" cells with one line, and the two "3" cells with another line. A line runs through the centers of non-obstacle cells, moving only horizontally or vertically between orthogonally adjacent cells.

The rules are:

• A line may not pass through an obstacle cell.
• Each cell may be used by at most one line. Hence the two lines never share a cell and never cross.
• The length of a line is the number of cell borders it crosses; a line joining two adjacent cells has length $1$.

Make the sum of the two line lengths as small as possible and output that minimum. If the two pairs cannot both be connected under these rules, the answer is $0$.

For example, in the first grid of the first sample below, both pairs can be connected with a minimum total line length of $18$.

The first line contains the number of data sets $T$.

The first line of each data set contains the number of rows $n$ and the number of columns $m$. ($2 \le n \le 9$, $2 \le m \le 9$)

The next $n$ lines describe the grid from the top row to the bottom row; each line contains $m$ integers separated by spaces. The meaning of each integer is:

• $0$: empty cell
• $1$: obstacle
• $2$: a cell marked "2"
• $3$: a cell marked "3"

Every grid contains exactly two cells marked "2" and exactly two cells marked "3".

For each data set, print on its own line the minimum possible sum of the two line lengths. Print $0$ if the two pairs cannot both be connected.