에리테아 원정

위대한 전사여,

그대의 임무는 사악한 에리테아의 왕을 처단하는 것이다.
그는 남쪽에 있는 자신의 영토에 있을 것이다.

신의 가호가 있기를,
이슬라디아의 왕.

이 명령을 수행하려면 그대는 남쪽으로 멀리 나아가 에리테아 영토로 들어가서, 은신처에 있는 그곳의 왕을 처단해야 한다. 영토는 위험한 요새들이 흩어져 있는 직사각형 지역이다. 지역은 뚫을 수 없는 성벽으로 둘러싸여 있어, 들어갈 수 있는 유일한 방법은 페가수스(하늘을 나는 말)를 타고 지역 안 어느 지점에 착륙하는 것뿐이다. 왕의 은신처 위치는 알려져 있으므로, 그대는 그 지점까지 도달하기만 하면 된다. 지역은 넓고 격자 모양의 도로로 덮여 있어, 그대는 이 도로를 따라 이동해야 한다. 요새의 망루에는 감시병들이 있어, 요새에 가까이 지날수록 발각될 위험이 커진다. 착륙 지점에서 왕이 있는 곳까지 가장 안전한 경로를 찾아야 한다.

형식적으로, 영토와 그 안의 도로를 나타내는 $m \times n$ 크기의 단위 정사각형 격자가 주어진다(여기서 $m$은 행의 수, $n$은 열의 수이다). 그대는 격자선(도로)을 따라 이동하며, 임의의 교차점(도로가 만나는 점)에서 다른 도로로 방향을 바꿀 수 있다. 각 요새는 서로 인접한 정사각형들의 집합이다. 요새 안으로는 들어갈 수 없으므로 경로는 요새의 내부를 결코 가로지르지 않지만, 요새의 경계에 놓인 도로 위로는 이동할 수 있다. 페가수스는 정확히 어떤 도로 교차점(출발점 $S$)에 착륙하고, 왕은 다른 도로 교차점(목적지 $D$)에 숨어 있다. 두 지점 모두 요새 내부에 있지는 않지만, 요새의 경계 위에 있을 수는 있다.

모든 도로 교차점에는 위험도가 매겨진다. 어떤 교차점에서 요새의 경계 위에 있는 점까지의 최단 도로 거리를 $d$라 하면, 그 교차점의 위험도는 $m + n - d$이다. 지역에는 요새가 적어도 하나 존재하므로 이 정의는 항상 잘 정의된다.

지도와 출발점, 목적지가 주어질 때, 격자선을 따라 $S$에서 $D$까지 가는 경로 중 경로 위 교차점들($S$와 $D$ 포함)의 위험도 합이 최소가 되는 경로를 찾아라. 경로는 어떤 요새의 내부도 가로질러서는 안 된다.

첫 번째 줄에 테스트 케이스의 수 $M$이 주어진다($1 \le M \le 10$). 이어서 각 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 격자의 행의 수와 열의 수가 주어지며, 두 값 모두 $1$ 이상 $80$ 이하이다. 둘째 줄에는 네 개의 정수가 주어지는데, 출발점(페가수스가 착륙한 곳)의 $y$, $x$ 좌표와 목적지(왕이 숨어 있는 곳)의 $y$, $x$ 좌표이다. 가로 격자선은 위에서 아래로 $0$부터 번호가 매겨져 $y$ 좌표가 되고, 세로 격자선은 왼쪽에서 오른쪽으로 $0$부터 번호가 매겨져 $x$ 좌표가 된다.

이 두 줄에 이어 지도의 각 행이 주어진다. 각 행은 그 행의 정사각형들을 나타내는 0과 1로 이루어진 문자열이다. 1은 해당 정사각형이 요새에 속함을, 0은 속하지 않음을 뜻한다. 지역의 너비는 각 문자열의 길이와 같고, 높이는 문자열의 개수와 같다.

각 테스트 케이스마다 착륙 지점에서 목적지까지 이르는 최소 위험 경로의 총 위험도를 한 줄에 하나씩 출력한다. 경로의 총 위험도는 그 경로 위 교차점들(출발점과 목적지 포함)의 위험도를 모두 더한 값이다. 출발점과 목적지 사이에 경로가 존재하지 않으면 대신 no solution을 출력한다.