Gridland

For years, computer scientists have tried to find efficient solutions to different computing problems. For some of them efficient algorithms are already known — these are the "easy" problems such as sorting, evaluating a polynomial, or finding the shortest path in a graph. For the "hard" ones only exponential-time algorithms are known. The Traveling Salesman Problem belongs to this latter group. Given a set of $N$ towns and the roads between them, the task is to compute the length of the shortest route that lets a salesman visit each town exactly once and return to the starting point.

The president of Gridland has hired you to write a program that computes the length of the shortest traveling-salesman tour of the towns in the country. In Gridland there is one town at each point of a rectangular grid. From every town, roads run in the eight directions North, Northwest, West, Southwest, South, Southeast, East, and Northeast, provided a neighbouring town exists in that direction. The distance between towns that are neighbours in the North–South or East–West direction is $1$ unit. Road lengths are measured by Euclidean distance. For example, the figure below shows $2 \times 3$ Gridland, i.e. a rectangular grid of size $2 \times 3$; there the shortest tour has length $6$.

Figure: A traveling-salesman tour in $2 \times 3$ Gridland.

The first line contains the number of scenarios.

For each scenario, a single line contains the grid dimensions $m$ and $n$ as two integers separated by a single space, satisfying $1 < m < 50$ and $1 < n < 50$.

For each scenario, print Scenario #i: on the first line, where i is the scenario number starting at $1$. On the second line, print the length of the shortest traveling-salesman tour rounded to two decimal places. Separate the outputs of consecutive scenarios with a single blank line.