Hiking

You like adventure, and hiking is one of your favorite hobbies. A novice is joining you on this trip, so you want to pick the easiest route on the map of the area.

The hiking area is a grid with $h$ rows and $w$ columns. Each cell is identified by its row number and column number, where $(0, 0)$ is the top-left cell and $(h-1, w-1)$ is the bottom-right cell. You are given a map that lists the height of every cell, together with the starting cell of your trip.

The difficulty of a route is the total energy spent on it. From one cell you can move to an adjacent cell in any of the eight directions: up, left, down, right and the four diagonals. You cannot leave the map, and you cannot enter a dangerous cell.

Moving to a cell of the same height spends 1 unit of energy. Moving to a cell that is $d$ units higher or lower spends $(d+1)^2$ units of energy.

You and your friend want to reach the highest cell in the grid. There is exactly one highest cell. Find the difficulty of the easiest route, the route that spends the least energy.

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

Each test case is given in the following format.

• The first line contains the height $h$ and the width $w$ of the grid. ($3 \le h \le 100$, $3 \le w \le 100$)
• The next $h$ lines describe the map. Each line is a string of $w$ characters. Each character is a digit from 0 to 9 giving the height of that cell, or # marking a dangerous cell. The digit 9 is the highest.
• The last line contains the starting position $x$ and $y$. ($0 \le x \le h-1$, $0 \le y \le w-1$) The starting cell is not a dangerous cell.

For each test case, print the energy needed for the easiest route on its own line. If there is no route from the starting position to the highest cell, print NO.

In the first example the easiest route is (0, 0) -> (1, 0) -> (2, 1) -> (2, 2) -> (2, 3). The energy spent on the four moves is 1, 4, 4 and 4.