산악 통로 찾기

등산가 Alp은 정사각형 모양의 산악 지대에서 북서쪽 모서리에 서 있으며, 반대편인 남동쪽 모서리로 가는 통로를 찾으려고 합니다.

Alp은 지금 산소가 필요 없는 고도에 있습니다. 하지만 이 출발 고도보다 조금이라도 더 높은 고도에서는 산소가 필요합니다. 산소가 필요한 경우, 가로 방향으로 한 걸음 이동할 때마다 산소 1단위를 소모합니다.

북서쪽 모서리는 위치 $(1, 1)$, 남동쪽 모서리는 위치 $(n, n)$입니다. $1 \le x, y \le n$인 각 지점 $(x, y)$의 고도는 정수입니다.

Alp은 가로 방향의 걸음을 이어서 이동합니다. 한 걸음은 북, 남, 동, 서 중 한 방향으로 한 칸 이동하는 것입니다. Alp은 정사각형 영역을 벗어날 수 없으며, 한 걸음에 고도를 $2$단위보다 많이 오르거나 내려갈 수 없습니다. 한 걸음의 출발 지점 또는 도착 지점의 고도가 산소를 필요로 한다면, Alp은 그 걸음에서 산소 1단위를 소모합니다.

$(1, 1)$에서 $(n, n)$까지 이동할 때 Alp이 소모해야 하는 산소의 최소 단위 수를 구하세요. 그러한 통로가 존재하지 않으면 존재하지 않는다고 출력하세요.

첫째 줄에는 Alp이 이동해야 하는 여행의 수를 나타내는 양의 정수 $T$가 주어집니다.

각 여행은 다음과 같이 주어집니다. 여행의 첫째 줄에는 정사각형 지대의 한 변의 길이를 나타내는 정수 $n$ ($1 \le n \le 25$)이 주어집니다. 이어지는 $n^2$개의 줄에는 각각 한 지점의 고도를 나타내는 정수가 하나씩 주어집니다. 고도는 다음 순서로 나열됩니다:

$(1, 1), (1, 2), (1, 3), \dots, (1, n), (2, 1), (2, 2), \dots, (n, 1), (n, 2), \dots, (n, n)$.

각 여행마다 한 줄을 출력합니다.

통로가 존재하면 소모되는 산소의 최소 단위 수를 출력합니다. 통로가 존재하지 않으면 CANNOT MAKE THE TRIP 메시지를 출력합니다.

연속한 여행의 출력 줄 사이에는 빈 줄 하나를 넣어 구분합니다.