Mountain Passage

Interview

Time limit1sMemory limit128 MB

Summary

Find the minimum count of steps that touch an elevation above the start height, moving on an n by n grid with height changes limited to 2 per step.

Level: Medium6 of 10
Topics: Graph, Shortest path, Heap, DFS
Solved: No attempts yet

Problem

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.

Input

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)$ .

Output

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.

Examples5

Example 1

Input

Expected output

5

CANNOT MAKE THE TRIP

Example 2
Input
```
1
1
42
```
Expected output
```
0
```
Example 3
Input
```
1
2
5
5
5
5
```
Expected output
```
0
```
Example 4
Input
```
1
2
1
3
3
1
```
Expected output
```
2
```
Example 5
Input
```
1
2
0
5
5
0
```
Expected output
```
CANNOT MAKE THE TRIP
```