T830132 逐级采集（collect）

采集机器人所在的区域可以看作一个 $H$ 行 $W$ 列的网格。每个格子是空地、障碍、出发点或采集点之一。 区域中恰有 $K$ 个采集点，等级分别为 $1,2,\ldots,K$，每个等级恰好出现一次。机器人从出发点出发，初始等级为 $1$。 机器人每次可以移动到上、下、左、右相邻且没有障碍的格子，每次移动花费 $1$ 单位时间。当机器人位于一个尚未采集的采集点，且自身等级不低于该采集点等级时，可以立即采集它。采集不花时间，每采集一个点，机器人自身等级增加 $1$。每个采集点只能被采集一次。 机器人可以不采集而直接经过某个采集点。即使该点等级高于机器人当前等级，它所在的格子仍然可以经过。已采集的格子也可以再次经过。 请计算采集完全部 $K$ 个点所需的最短时间。保证机器人能够采集完全部采集点。

第一行一个整数 $T$，表示数据组数。 每组数据第一行三个整数 $H,W,K$。 接下来 $H$ 行，每行一个长度为 $W$ 的字符串，描述网格。其中 `S` 表示出发点，`X` 表示障碍，`.` 表示空地，数字字符 `1` 至 `9` 表示对应等级的采集点。 保证每组恰有一个 `S`，每个等级 $1,2,\ldots,K$ 对应的数字字符恰好出现一次，且不出现其他数字字符。剩余格子都是 `X` 或 `.`。

每组数据输出一行一个整数，表示最短时间。

机器人可以从左上角出发，向右移动两次，再向下移动两次，到达唯一的采集点并立即完成采集，总时间为 $4$。起点和终点在横、纵方向上各相隔两格，因此至少需要移动四次。 ## 样例 2 见 `考生目录/collect/collect2.in` 与 `考生目录/collect/collect2.ans`。该样例满足测试点 $1\sim6$ 的约束。 ## 样例 3 见 `考生目录/collect/collect3.in` 与 `考生目录/collect/collect3.ans`。该样例满足测试点 $7\sim12$ 的约束。 ## 样例 4 见 `考生目录/collect/collect4.in` 与 `考生目录/collect/collect4.ans`。该样例满足测试点 $13\sim20$ 的约束。 ## 样例 5 见 `考生目录/collect/collect5.in` 与 `考生目录/collect/collect5.ans`。该样例满足测试点 $13\sim20$ 的约束。 ## 样例 6 见 `考生目录/collect/collect6.in` 与 `考生目录/collect/collect6.ans`。该样例满足测试点 $13\sim20$ 的约束。 ## 数据范围 对于所有数据，保证 $1\le T\le10$。每组数据中，$1\le H,W\le1000$，$1\le K\le9$，且全部采集点均可完成采集。同一输入文件中，所有组的 $HW$ 之和不超过 $2\times10^6$。 | 测试点编号 | 附加限制（每组均满足） | | :--------: | :--------------------: | | $1\sim6$ | 没有障碍格 | | $7\sim12$ | $HW\le120$ | | $13\sim20$ | 无 |