描述

背景

多年来，计算机科学家一直在尝试为不同的计算问题寻找高效的解决方案。对于其中一些问题，已经有了高效的算法，例如排序、多项式求值或在图中寻找最短路径等“简单”问题。而对于另一些“困难”问题，目前仅知道指数时间复杂度的算法。旅行商问题（Traveling-Salesman Problem）就属于后者。给定一组$N$个城镇和它们之间的道路，该问题的目标是计算出一条最短路径，使得一名销售员能够访问每个城镇恰好一次并最终返回起点。

问题

Gridland的总统雇佣您设计一个程序，用于计算该国城镇的最短旅行商路径的长度。在Gridland中，每个城镇位于矩形网格的一个点上。道路从每个城镇向八个方向延伸：北、西北、西、西南、南、东南、东和东北，只要该方向上存在相邻的城镇即可。相邻城镇在南北或东西方向上的距离为$1$单位。道路的长度由欧几里得距离衡量。例如，图7展示了$2 \times 3$的Gridland，即一个$2$行$3$列的矩形网格。在$2 \times 3$的Gridland中，最短的旅行商路径长度为$6$。

输入

第一行包含场景的数量。
对于每个场景，网格的维度$m$和$n$将在一行中给出，作为两个整数，中间用单个空格分隔，满足$1 < m < 50$和$1 < n < 50$。

输出

每个场景的输出以一行“Scenario #i:”开始，其中$i$是从$1$开始的场景编号。接下来一行输出最短旅行商路径的长度，保留两位小数。每个场景的输出以空行结束。

输入样例 1

2
2 2
2 3

输出样例 1

Scenario #1:
4.00

Scenario #2:
6.00

来源

Northwestern Europe 2001