등산

당신은 모험을 좋아해서 등산이 취미 중 하나다. 이번 등산에는 초보자가 함께 가므로, 지역 지도에서 가장 쉬운 경로를 고르려고 한다.

등산 지역은 세로 $h$칸, 가로 $w$칸의 격자다. 각 칸은 행 번호와 열 번호로 나타내고, $(0, 0)$이 왼쪽 위 칸, $(h-1, w-1)$이 오른쪽 아래 칸이다. 모든 칸의 높이가 적힌 지도와 출발 칸이 주어진다.

경로의 난이도는 그 경로를 지나는 데 쓰는 에너지의 총합이다. 한 칸에서 인접한 여덟 방향, 즉 위, 왼쪽, 아래, 오른쪽과 네 대각선 방향의 칸으로 이동할 수 있다. 지도 밖으로는 나갈 수 없고, 위험한 칸에는 들어갈 수 없다.

높이가 같은 칸으로 이동하면 에너지를 1 쓴다. 높이가 $d$만큼 더 높거나 더 낮은 칸으로 이동하면 에너지를 $(d+1)^2$ 쓴다.

당신과 친구는 격자에서 가장 높은 칸에 도달하려고 한다. 가장 높은 칸은 하나뿐이다. 쓰는 에너지가 가장 적은 경로, 즉 가장 쉬운 경로의 난이도를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 20$)

이어서 각 테스트 케이스가 다음 형식으로 주어진다.

• 첫째 줄에 격자의 세로 길이 $h$와 가로 길이 $w$가 주어진다. ($3 \le h \le 100$, $3 \le w \le 100$)
• 다음 $h$개 줄에 지도가 주어진다. 각 줄은 길이가 $w$인 문자열이고, 각 문자는 칸의 높이를 나타내는 숫자 0에서 9까지 중 하나이거나 위험한 칸을 나타내는 #이다. 숫자 9가 가장 높다.
• 마지막 줄에 출발 위치 $x$와 $y$가 주어진다. ($0 \le x \le h-1$, $0 \le y \le w-1$) 출발 칸은 위험한 칸이 아니다.

각 테스트 케이스마다 가장 쉬운 경로에 필요한 에너지를 한 줄에 출력한다. 출발 위치에서 가장 높은 칸으로 가는 경로가 없으면 NO를 출력한다.

첫 번째 예제에서 가장 쉬운 경로는 (0, 0) -> (1, 0) -> (2, 1) -> (2, 2) -> (2, 3)이다. 각 이동에 쓰는 에너지는 차례로 1, 4, 4, 4다.