Honeymoon Hike#2533
Emma and her husband Eric are spending their honeymoon on a hiking trip, traveling from one cabin to another each day. Unfortunately, Eric is not as fit as Emma and tires quickly. Emma wants to avoid starting their marriage with any serious conflict (and also needs someone to keep her warm at night), so she decides to plan the hikes in a way that keeps them comfortable for Eric.
Over the last few days, Emma has noticed that Eric does not get tired so much from the total distance of the hike or the overall ascent. Instead, the larger the difference between the highest and the lowest elevation during the day's route, the more exhausted he becomes. Emma thinks this is because of psychological reasons—it sounds much harder to climb once from meters up to meters than to climb from up to meters ten times, even though the latter involves twice as much climbing.
Given a map with elevation values, help Emma find a path from the top-left corner (starting cabin) to the bottom-right corner (destination cabin), minimizing the difference between the highest and lowest elevation on the route. Movement is only allowed in the four cardinal directions (no diagonals).
The first line contains the number of scenarios. Each scenario starts with a number (2 \le n \le 100), the size of the area. The terrain elevations are given as an n \times n integer matrix h_{i,j} (0 \le h_{i,j} \le 200) on lines, each containing space-separated elevations.
For each scenario, print a line "Scenario #i:", where is the scenario number starting from . On the next line, print a single integer—the minimum possible difference between the highest and lowest elevation on an optimal path. End each scenario's output with a blank line.
Example 1