Mountain Passage

A mountain climber named Alp stands at the northwest corner of a square patch of mountainous terrain and wants to find a passage to the opposite (southeast) corner.

Alp currently stands at an elevation at which oxygen is not needed. At any elevation strictly higher than this starting elevation, oxygen is required. When oxygen is required, it is consumed at a rate of one unit per horizontal step.

The northwest corner is at position $(1, 1)$ and the southeast corner is at position $(n, n)$. The elevation of every point $(x, y)$ with $1 \le x, y \le n$ is an integer.

Alp travels in a series of horizontal steps. Each step moves Alp one unit north, south, east, or west. Alp must stay inside the square region and cannot climb or descend more than $2$ units of elevation in a single step. If the elevation at the beginning of a step or at the end of a step requires oxygen, Alp consumes one unit of oxygen during that step.

Report the minimum number of units of oxygen Alp must consume to travel from $(1, 1)$ to $(n, n)$, or report that no such passage exists.

The first line contains a positive integer $T$: the number of trips Alp must make.

Each trip is described as follows. The first line of a trip contains an integer $n$ ($1 \le n \le 25$), the side length of the square terrain. The next $n^2$ lines each contain a single integer giving the elevation of one point. The elevations are listed in this order:

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

For each trip, print a single line.

If a passage exists, print the minimum number of units of oxygen consumed. If no passage exists, print the message CANNOT MAKE THE TRIP.

Separate the output lines for consecutive trips with a single blank line.