描述

现代办公大楼的建设已经变得非常标准化。预制模块根据客户需求进行组合，从遥远的工厂运输到施工现场并进行组装。然而，仍有一些任务需要仔细规划，例如暖通系统的管道布线。

现代办公大楼由若干方形模块组成，每层有一个服务模块，热水从这里通过供暖管道泵送至其他模块。每个模块（包括服务模块）必须通过管道与恰好两个相邻模块（2 至 4 个可选）相连。因此，管道必须形成一个回路：从服务模块出发，经过每个模块恰好一次，最后返回服务模块。

由于模块之间的物理特性不同，相邻模块之间的管道铺设成本也不同。例如，某些模块之间有厚墙，会增加管道铺设成本。你的任务是：给定办公大楼某一层的描述，计算最便宜的管道布线方案。

输入

输入的第一行是一个整数，表示需要处理的楼层数量。接下来的每个楼层描述由以下部分组成：

• 第一行：两个整数 $r$ 和 $c$（$2 \leq r \leq 10$，$2 \leq c \leq 10$），表示该楼层的模块布局为 $r \times c$。
• 接下来的 $2r + 1$ 行：楼层的 ASCII 描述，每行包含 $2c + 2$ 个字符（包括换行符）。所有楼层均为严格矩形，且模块数量为偶数。

楼层描述说明：

• # 表示外墙或不可通行的区域。
• 数字 '0' 到 '9' 表示模块之间的内墙，其数值代表在该处铺设管道的成本（参见样例输入）。

输出

对于每个测试用例，输出一行，表示最便宜管道方案的总成本。

输入数据 1

3
4 3
#######
# 2 3 #
#1#9#1#
# 2 3 #
#1#7#1#
# 5 3 #
#1#9#1#
# 2 3 #
#######
4 4
#########
# 2 3 3 #
#1#9#1#4#
# 2 3 6 #
#1#7#1#5#
# 5 3 1 #
#1#9#1#7#
# 2 3 0 #
#########
2 2
#####
# 1 #
#2#3#
# 4 #
#####

输出数据 1

28
45
10

来源

2004 年西北欧地区竞赛