Sheep Frenzy

Time limit1sMemory limit256 MB

Summary

Move across a grid with mountains to reach every sheep and spend one second eating each, using the fewest seconds, or report impossible.

Level: Medium7 of 10
Topics: Dynamic programming, BFS, Bit manipulation
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples2

Example 1

Input

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

Expected output

3
impossible

Example 2
Input
```
1
1 2
U#
```
Expected output
```
2
```