Robot In A Room

You just bought a robotic vacuum cleaner, and you like watching it explore your room. After a long look, you worked out the rules it follows.

• Moving one cell takes one minute.
• The battery holds $d$ units, so a full charge is worth $d$ moves.
• Every move and every turn costs one minute and one unit of battery.
• When the cell straight ahead is a wall or an obstacle, the robot turns right 90 degrees in place.
• Outlets sit in the walls, so the robot cannot enter an outlet cell. It charges only from a cell that touches an outlet horizontally or vertically, never diagonally.
• The robot checks its battery after every one-minute action (a move or a turn). If the remaining battery $b$ satisfies $2b \le d$ and the current cell touches an outlet, the robot stops there and charges until full. Charging takes one minute per unit of battery added.
• If the battery reaches 0 and the robot cannot charge, it stops for good.

You just spilled your drink on the carpet. The robot cleans the mess the moment it enters that cell, and cleaning costs no time and no battery. Given the robot's starting position and the position of your spill, find how many minutes the robot needs to reach the mess.

The first line holds the number of test cases $T$ ($1 \le T \le 500$).

The first line of each test case holds two integers $n$ and $d$ separated by a space. The room is an $n \times n$ grid of unit squares, and $d$ is the number of moves a fully charged robot can make ($5 \le n \le 20$, $15 \le d \le 30$).

The next $n$ lines each hold $n$ characters.

Each test case holds exactly one r and exactly one m.

For each test case print one line in the form Case x: y, where $x$ is the test case number starting at 1 and $y$ is the number of minutes the robot needs to reach the mess. If the robot never reaches the mess, print NEVER in place of $y$.