Sheep Frenzy

Ulgr the Unpleasantsmelling eats sheep. On every level he has to eat all of the sheep, and he wants to finish as fast as possible. Write a program that computes the shortest time.

The board is an $H \times W$ grid. Each cell is one of the following.

• U: the cell Ulgr starts on. Every level has exactly one.
• #: a sheep. Sheep never move.
• .: grass.
• X: a mountain. Ulgr cannot step on it.

Ulgr acts once per second. One action is a move to an adjacent cell up, down, left or right, or eating a sheep on the cell he is standing on. He can eat a sheep only while standing on the same cell as that sheep.

The first line contains the number of test cases $T$. Each test case begins with a line holding the height $H$ and the width $W$ of the board. The next $H$ lines each contain $W$ characters describing the board.

• $0 < T \le 100$
• $0 < H, W \le 50$
• Each test case has at least 1 sheep and at most 16 sheep.
• Each test case contains exactly one U.
• Every mountain is marked X, so neither Ulgr nor any sheep starts on a mountain.

For each test case, print one line with the minimum number of seconds Ulgr needs to eat every sheep on that level. If he cannot eat all of the sheep, print impossible instead.