The Erythea Campaign

O' mighty warrior,

Thy mission is to slay the foul king of Erythea.
Thou shall find him in his realm in the south.

God bless you,
King of Isladia.

To carry out this order you must travel far to the south, enter the realm of Erythea, and slay its king at his hiding place. The realm is a rectangular region dotted with dangerous strongholds. Impenetrable walls surround the region, so the only way in is to land your Pegasus (flying horse) at some point inside it. The king's hiding place is known, so you only need to reach that location. Because the area is large and crossed by grid-like roads, you must travel along those roads. Guards watch from the towers of the strongholds: the closer you pass to a stronghold, the more likely you are to be seen. You must find the safest route from your landing point to the king.

Formally, you are given an $m \times n$ grid of unit squares that models the realm and its roads (here $m$ is the number of rows and $n$ the number of columns). You travel along the grid lines (roads) and may turn onto another road at any intersection (road crossing). Each stronghold is a set of adjacent squares. You may not enter a stronghold, so your path never crosses the interior of a stronghold, although you may travel on a road that lies on a stronghold's boundary. You land your Pegasus exactly on a road crossing (the source $S$), and the king hides on another road crossing (the destination $D$). Neither point lies inside a stronghold, but either may sit on a stronghold boundary.

Every road crossing has a risk level. Let $d$ be the shortest road distance from the crossing to a point that lies on the boundary of a stronghold; then the crossing's risk level is $m + n - d$. At least one stronghold is present, so this definition is always well defined.

Given the map together with the source and destination, find a path from $S$ to $D$ that runs along grid lines and minimizes the sum of the risk levels of the crossings on the path (including $S$ and $D$). The path may not cross the interior of any stronghold.

The first line contains a single integer $M$, the number of test cases ($1 \le M \le 10$). The test cases follow.

Each test case begins with a line containing the number of rows and the number of columns of the grid, both between $1$ and $80$. The second line contains four integers: the $y$ and $x$ coordinates of the source (where the Pegasus lands) followed by the $y$ and $x$ coordinates of the destination (where the king hides). Horizontal grid lines are indexed from top to bottom starting at $0$ (giving the $y$ coordinate), and vertical grid lines from left to right starting at $0$ (giving the $x$ coordinate).

After these two lines come the rows of the map. Each row is a string of 0s and 1s describing the squares of that row: a 1 means the corresponding square belongs to a stronghold, a 0 means it does not. The width of the region equals the length of each string and its height equals the number of strings.

For each test case print, on its own line, the total risk of the minimum-risk path from the landing point to the destination. The total risk of a path is the sum of the risk levels of the crossings on it (including the source and the destination). If no path exists between the source and the destination, print no solution instead.