自 IDI Open ’09 以来，我编写了许多旨在帮助我入睡的数羊程序。遗憾的是，这些程序效果都不好，所以我过去几年几乎每天晚上都在诅咒那些邪恶的动物。失眠给了我不少空闲时间，我便用这些时间创造了一款名为“Sheep Frenzy”的新游戏。

玩家控制“令人不快的”Ulgr，他的目标是尽快吃掉每一关中的所有羊。奇怪的是，尽管我已经玩得很好了，但这仍然不能让我从这些作恶者身上获得复仇的快感。这就是我需要你帮助的原因。你需要编写一个程序，计算出让 Ulgr 在棋盘上移动以尽快吃掉所有羊的最佳路径。

棋盘是一个 $H \times W$ 的网格，每个单元格代表以下内容之一：

• 'U' - “令人不快的”Ulgr 的起始位置。他喜欢吃羊，而你将帮助他实现这一目标。
• '#' - 羊。它们显然又瞎又聋，也没有嗅觉，所以即使你走过去吃它们，它们也不会移动。
• '.' - 草地。别争了，这就是草地。
• 'X' - 山脉。你（Ulgr）不能走在这些格子上。好吧，老实说你可以走，但请不要这样做。如果你走上去，游戏会卡死。

Ulgr 每秒钟移动一次。一次移动包括吃掉一只羊，或者向左、向右、向上、向下移动一个单元格。他只有在与羊处于同一个单元格时才能吃掉它。

输入格式

输入的第一行包含一个整数 $T$，表示接下来的测试用例数量。每个测试用例以一行包含两个数字 $H$ 和 $W$ 开始，分别表示该关卡网格的高度和宽度。接下来是 $H$ 行，每行包含 $W$ 个字符，描述该部分的网格。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示 Ulgr 吃掉该关卡所有羊所需的最短时间（以秒为单位）。如果无法吃掉所有的羊，则输出 impossible。

数据范围

• $0 < T \leq 100$
• $0 < H, W \leq 50$
• 每个测试用例中羊的数量至少为 1 只，且不超过 16 只。
• 每个测试用例包含且仅包含一个 'U'。
• 棋盘上的所有山脉都标记为 'X'。也就是说，Ulgr 和任何羊都不会出现在山脉上。

样例

输入格式 1

2
2 2
U.
.#
3 5
#..X#
..XXX
.U...

输出格式 1

3
impossible