Протягом багатьох років комп'ютерні спеціалисти намагаються знайти ефективні розв'язки для різноманітних обчислювальних задач. Для деяких з них ефективні алгоритми вже існують, це "легкі" задачі, такі як сортування, обчислення многочлену чи знаходження найкоротшого шляху в графі. Для "важких" задач відомі лише алгоритми з експоненціальним часом. Задача бродячого продавця належить до отанньої групи. Знаючи множину міст N та дороги між цими містами, задача полягає у тому, щоб обчислити найкоротший шлях, який дасть можливість продавцю відвідати кажне з міст лише один раз і повернутись у початкову точку.
Президент сітчатої країни найняв вас розробити програму, яка обчислює довжину найкоротшого тура бродячего торговця для міст у його країні. У сітчатій країні кожне місто розміщено у кожній з точок прямокутної сітки. Дороги напрямлені з кожного міста у напрямку півночі, північного заходу, заходу, південного сходу, півдня, південного сходу, сходу та північного сходу при умові, що в цьому напрямку є сусіднє місто. Відстань між сусідніми містами у напрямку схід-захід або північ-південь дорівнює 1 одиниці. Довжина дороги вимірюється евклідовою відстанню. Наприклад, на рисунку нижче показано сітчату країну 2×3, тобто прямокутна сітка розміром 2 на 3. У сітчатій страїні 2×3 самий короткий тур має довжину 6.
Тур бродячего торговца по сетчатой стране 2×3
Перший рядок містить кількість тестів. Для кожного тестового випадку задано розміри сітки m (1 < m < 50) та n (1 < n < 50), поданими двома цілими числами у одному рядку і відокремленими одним пропуском.
Вихід для кожного тестового випадку починається з рядка, який містить "Scenario #i:", де i - це номер тестового випадку, починаючи з 1. У наступному рядку виведіть довжину найкоротшого тура бродячого торгівця, округлену до двох десяткових цифр. Вихідні дані для сусідніх тестових випадків відокремлюйте порожнім рядком.