방 안의 로봇 청소기

새로 산 로봇 청소기가 방을 돌아다니는 모습을 한참 지켜본 끝에 다음 규칙을 알아냈다.

• 한 칸 이동하는 데 1분이 걸린다.
• 배터리 용량은 $d$이고, 가득 충전하면 $d$번 움직인다.
• 이동 한 번과 회전 한 번은 각각 1분과 배터리 1을 쓴다.
• 바로 앞이 벽이나 장애물이면 제자리에서 오른쪽으로 90도 돈다.
• 콘센트는 벽에 박혀 있어서 로봇이 콘센트 칸으로 들어가지 못한다. 충전은 콘센트와 상하좌우로 맞닿은 칸에서만 하고, 대각선은 맞닿은 것으로 치지 않는다.
• 1분짜리 동작(이동이나 회전)을 마칠 때마다 배터리를 확인한다. 남은 배터리 $b$가 $2b \le d$를 만족하고 지금 서 있는 칸이 콘센트와 맞닿아 있으면, 그 자리에 멈춰 가득 찰 때까지 충전한다. 충전은 배터리 1을 채우는 데 1분이 걸린다.
• 배터리가 0이 되었는데 충전도 못 하면 로봇은 그대로 멈춘다.

방금 카펫에 음료를 쏟았다. 로봇은 오물이 있는 칸에 들어서는 순간 그 자리를 치우고, 청소 자체에는 시간도 배터리도 들지 않는다. 로봇의 시작 위치와 오물의 위치가 주어질 때, 로봇이 오물에 닿기까지 몇 분이 걸리는지 구하라.

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

각 테스트 케이스의 첫 줄에는 두 정수 $n$과 $d$가 공백을 사이에 두고 주어진다. 방은 한 변이 $n$인 $n \times n$ 격자이고, $d$는 가득 충전한 로봇이 움직일 수 있는 횟수다 ($5 \le n \le 20$, $15 \le d \le 30$).

이어지는 $n$개의 줄에는 각각 $n$개의 문자가 주어진다.

각 테스트 케이스에 r와 m은 정확히 하나씩 있다.

각 테스트 케이스마다 한 줄에 Case x: y 형식으로 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 로봇이 오물에 닿기까지 걸리는 시간을 분 단위로 나타낸 값이다. 로봇이 오물에 영영 닿지 못하면 $y$ 자리에 NEVER를 출력한다.