Протягом багатьох років комп'ютерні спеціалисти намагаються знайти ефективні розв'язки для різноманітних обчислювальних задач. Для деяких з них ефективні алгоритми вже існують, це "легкі" задачі, такі як сортування, обчислення многочлену чи знаходження найкоротшого шляху в графі. Для "важких" задач відомі лише алгоритми з експоненціальним часом. Задача бродячого продавця належить до отанньої групи. Знаючи множину міст \textbf{N} та дороги між цими містами, задача полягає у тому, щоб обчислити найкоротший шлях, який дасть можливість продавцю відвідати кажне з міст лише один раз і повернутись у початкову точку. Президент сітчатої країни найняв вас розробити програму, яка обчислює довжину найкоротшого тура бродячего торговця для міст у його країні. У сітчатій країні кожне місто розміщено у кожній з точок прямокутної сітки. Дороги напрямлені з кожного міста у напрямку півночі, північного заходу, заходу, південного сходу, півдня, південного сходу, сходу та північного сходу при умові, що в цьому напрямку є сусіднє місто. Відстань між сусідніми містами у напрямку схід-захід або північ-південь дорівнює \textbf{1} одиниці. Довжина дороги вимірюється евклідовою відстанню. Наприклад, на рисунку нижче показано сітчату країну \textbf{2}×\textbf{3}, тобто прямокутна сітка розміром \textbf{2} на \textbf{3}. У сітчатій страїні \textbf{2}×\textbf{3} самий короткий тур має довжину \textbf{6}. \includegraphics{https://static.e-olymp.com/content/31/319d9327e3de12fa8f6cce888c87f7250ee03513.jpg} Тур бродячего торговца по сетчатой стране \textbf{2}×\textbf{3} \InputFile Перший рядок містить кількість тестів. Для кожного тестового випадку задано розміри сітки \textbf{m} (\textbf{1} < \textbf{m} < \textbf{50}) та \textbf{n} (\textbf{1} < \textbf{n} < \textbf{50}), поданими двома цілими числами у одному рядку і відокремленими одним пропуском. \OutputFile Вихід для кожного тестового випадку починається з рядка, який містить "\textbf{Scenario #i:}", де \textbf{i} - це номер тестового випадку, починаючи з \textbf{1}. У наступному рядку виведіть довжину найкоротшого тура бродячого торгівця, округлену до двох десяткових цифр. Вихідні дані для сусідніх тестових випадків відокремлюйте порожнім рядком.