Медовый поход
Эмма отправилась в поход с Эриком, своим недавно женившимся мужем, в их медовый месяц. Каждый день они переходят от одной хижины к другой. К сожалению, Эрик не так вынослив, как Эмма, и постепенно устает. Поскольку Эмма не хочет начинать их только что созданный брак с серьезного конфликта (и ей нужен кто-то, чтобы согревать ее по ночам), она решает планировать следующие дневные маршруты так, чтобы они не были слишком утомительными для Эрика.
В последние дни Эмма обнаружила удивительный факт о своем муже. Он устает не столько от длины их ежедневного маршрута или общего количества метров, которые им пришлось подняться. Вместо этого Эрик устает больше, чем больше разница между самой высокой и самой низкой точкой сегодняшнего маршрута. Эмма предполагает, что это связано с психологическими факторами. Просто звучит намного сложнее подняться один раз с 500 метров до 1500 метров, чем подняться с 200 до 400 метров десять раз, хотя во втором случае вы поднялись вдвое больше.
Имея карту высот местности, вы должны помочь Эмме найти путь, который минимизирует разницу между самой высокой и самой низкой высотой, чтобы Эрик не чувствовал себя таким уставшим. Хижина, из которой они начинают, находится в верхнем левом углу, а их пункт назначения - в нижнем правом углу карты. Они могут двигаться в любом из четырех основных направлений, но не по диагонали.
Входные данные
Первая строка содержит количество сценариев. Каждый сценарий начинается с числа n (2 ≤ n ≤ 100), размера области. Высоты местности заданы в виде целочисленной матрицы n×n (h_i_{,j}) (0 ≤ h_i_{,j} ≤ 200) на n строках, где каждая строка содержит n высот, разделенных пробелами.
Выходные данные
Вывод для каждого сценария начинается со строки, содержащей "Сценарий #i:", где i - номер сценария, начиная с 1. Затем выведите одну строку, содержащую разницу между самой высокой и самой низкой высотой на оптимальном пути. Завершите вывод для сценария пустой строкой.