Woburn Challenge 2001

We seem to have forgotten about our lost SAS agent (from problem ~1~). It's time for John Patrick Mason to leave the men's camp on Temptation Island. Not by choice. Every man decided that he was a threat to their respective girlfriends and thus put a block on him. (Don't know what a block means? You clearly haven't been watching enough TV!) Deciding that it was no longer worthwhile to remain on the island, he decides to steal a bobsled from the Jamaican bobsled team that just happens to be partying it up at the women's camp. With the bobsled, he must move from the women's camp at the northwest corner of the island to the extraction point on the southeast corner of the island. However, you know that bobsleds have no motors and thus rely on momentum to move.

The bobsled can gain momentum if it moves downhill (e.g. it gains ~4~ units of momentum by moving from a point ~5~ metres high to an adjacent point ~1~ metre high). Similarly, moving uphill results in a loss of momentum units. Amazingly, this bobsled has been designed to be frictionless and thus loses no momentum on flat terrain. Lastly, when you change direction, all momentum is lost ("Why," you ask? How else is it supposed to turn on a frictionless surface without stopping first?). Clearly, since it is the momentum keeping you moving, you can't go anywhere with negative momentum. However, since the ground is frictionless, you can move with ~0~ momentum but only downhill or on level terrain.

You can move in any of the ~8~ cardinal directions but must not fall off the island. If you do, you will be immediately consumed by a ring of hungry sharks that encircle the island. You have obtained a topographical map of the island which lists the elevation at each grid location on the island. Note that the island is a square. Mason would like to leave the island with as much momentum as possible, since this makes for a better slow-motion escape scene.

Input Specification

The first line contains ~T~, the number of test cases to follow.
Each test case consists of a positive number ~N~ ~(2 \le N \le 100)~ representing the size of the island.
This is followed by an ~N \times N~ grid of integers representing heights at different parts of the island. No height will exceed ~100~ and all entries will be separated by a single space.

Output Specification

For each test case output the maximum amount of momentum with which Mason can leave the island, or Trapped! (remember, if there is no exclamation mark, all is lost) if he cannot reach the extraction point.

Sample Input

2
5
6 4 4 2 6
7 8 5 3 7
4 2 4 4 3
7 1 3 6 5
8 6 3 1 2
4
6 5 4 3
5 4 3 2
4 3 7 3
3 2 3 4

Sample Output

1
Trapped!