그리드랜드

컴퓨터 과학자들은 오랫동안 다양한 계산 문제에 대한 효율적인 해법을 찾아 왔습니다. 정렬, 다항식 값 계산, 그래프에서 최단 경로 찾기처럼 이미 효율적인 알고리즘이 알려진 "쉬운" 문제도 있지만, "어려운" 문제에는 지수 시간 알고리즘만 알려져 있습니다. 외판원 문제(Traveling Salesman Problem)는 후자에 속합니다. $N$개의 도시와 도시들을 잇는 도로가 주어질 때, 외판원이 모든 도시를 정확히 한 번씩 방문하고 출발점으로 돌아오는 가장 짧은 경로의 길이를 구하는 문제입니다.

그리드랜드의 대통령이, 나라 안 도시들에 대한 최단 외판원 순회 경로의 길이를 계산하는 프로그램을 여러분에게 의뢰했습니다. 그리드랜드에서는 직사각형 격자의 각 격자점마다 도시가 하나씩 있습니다. 모든 도시에서는 북, 북서, 서, 남서, 남, 남동, 동, 북동의 여덟 방향으로 도로가 뻗어 있으며, 그 방향에 이웃한 도시가 있을 때에만 도로가 존재합니다. 남북 방향 또는 동서 방향으로 이웃한 두 도시 사이의 거리는 $1$입니다. 도로의 길이는 유클리드 거리로 잽니다. 예를 들어 아래 그림은 $2 \times 3$ 그리드랜드, 즉 가로세로 $2 \times 3$ 크기의 격자를 나타내며, 이때 최단 순회 경로의 길이는 $6$입니다.

그림: $2 \times 3$ 그리드랜드에서의 외판원 순회 경로.

첫째 줄에 시나리오의 개수가 주어집니다.

각 시나리오마다 한 줄에 격자의 크기 $m$과 $n$이 공백 하나로 구분된 두 정수로 주어집니다. 두 값은 $1 < m < 50$과 $1 < n < 50$을 만족합니다.

각 시나리오에 대해, 첫째 줄에 Scenario #i:를 출력합니다. 여기서 i는 $1$부터 시작하는 시나리오 번호입니다. 둘째 줄에는 최단 외판원 순회 경로의 길이를 소수점 아래 둘째 자리까지 반올림하여 출력합니다. 서로 이웃한 두 시나리오의 출력 사이에는 빈 줄을 하나 넣습니다.