H - Kraina Kratki

Od lat informatycy próbują znaleźć wydajne rozwiązania do różnorodnych problemów obliczeniowych. Dla niektórych z nich takie algorytmy zostały znalezione. Do problemów tych, nazywanych "łatwymi" należy na przykład sortowanie, obliczanie wartości wielomianu w danym punkcie albo znajdowanie najkrótszej drogi w grafie. Dla problemów "trudnych" są znane tylko algorytmy o wykładniczym czasie działania. Do takich właśnie problemów należy problem komiwojażera: mając dany zbiór N miast i długości dróg pomiędzy miastami, należy znaleźć najkrótszą ścieżkę taką, która przechodzi przez każde miasto dokładnie raz i wraca do miasta początkowego.

Rys. 1 Ścieżka komiwojażera w krainie o rozmiarze 2 x 3.

Zadanie

Prezydent Krainy Kratki zatrudnił Cię do napisania programu, który oblicza długość najkrótszej ścieżki komiwojażera dla wszystkich miast w państwie. W Krainie Kratki miasta ułożone są na prostokątnej kratownicy. W każdym punkcie kratownicy znajduje się jedno miasto. Z każdego miasta wychodzą drogi do najbliższego miasta w kierunkach wschodnim, zachodnim, północnym, południowym, północno-wschodnim, północno-zachodnim, południowo-wschodnim i południowo-zachodnim. Jeżeli w danym kierunku nie ma żadnego miasta, to droga w tym kierunku nie istnieje. Długości dróg do sąsiadujących miast w kierunkach wschodnim, zachodnim, północnym i południowym wynoszą 1 jednostkę. W pozostałych przypadkach długości te wynoszą pierwiastek kwadratowy z dwóch. Na rysunku 1 jest przedstawiona kraina o rozmiarze 2 x 3. Najkrótsza ścieżka komiwojażera w tym przypadku wynosi 6.

Wejście

W pierwszej linii podana jest liczba testów. Każdy test składa się z jednej linii zawierającej dwie liczby całkowite m i n (1 < m, n < 55) oznaczające rozmiary Krainy Kratki.

Wyjście

Dla każdego testu podaj jedną linię zawierającą długość najkrótszej ścieżki komiwojażera zaokrągloną do dwóch miejsc po przec

Przykładowe wejście

Przykładowe wyjście