SP11477 DCEPC706 - Meeting For Party

Ankur、Anuja 和 Jyoti 准备在某地聚会。他们的家分别位于一个 $M \times N$ 的矩形网格中不同的地方。他们希望以最短的时间到达同一个地点开始聚会。 这个 $M$ 行 $N$ 列的矩形网格中，有些点是不可通行的（用 `#` 表示），因此没人会经过这些点。他们只能在可通行的点（用 `.` 表示）上移动。他们也可以选择在网格外的某个位置会合。假设网格外面的所有位置都是可通行的。他们的房子仅安置在可通行的点上，他们无法在不可通行的点聚会。每次移动时，他们可以向北、南、东、西四个方向移动到相邻的可通行点，每次移动耗时 1 个单位时间。同时，他们也可以选择在某个可通行点等待。 请你计算他们三个在网格内外能够会合的最短时间。 **注意：可以假设他们总能在某个点会合。**

第一行输入一个整数 $T$，表示有多少个测试用例。 对于每个测试用例，第一行包含两个用空格分隔的整数 $M$ 和 $N$，分别代表网格的行数和列数。 接下来的 $M$ 行，每行有 $N$ 个字符（无空格）。字符可以是：`#`（不可通行）、`.`（可通行）、`1`（Ankur 的房子）、`2`（Anuja 的房子）、`3`（Jyoti 的房子）。每个测试用例中会有且仅有一个 `1`、一个 `2` 和一个 `3`。

针对每个测试用例，输出一行结果，表示他们能够会合的最短时间。 ## 数据范围 - $1 \le T \le 10$ - $1 \le M, N \le 100$ **本翻译由 AI 自动生成**