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