50K Celebration Warmup Contest

Hippo and his two friends lost their path in a jungle. In this days jungle is most dangerous place. The jungle has lots of tunnels. Also there lived some brutal animals in the dangerous zone(the cell ‘D’). Now Hippo and his two friends want to go to safe places(‘#’) as fast as possible i.e. in minimum times.

In this problem you are given the jungle-map asa grid. Where ‘A’,’B’,’C’ denotes the position of Hippo and his two friends. ’D’ indicates dangerous place. No one can stay this cell.  ‘#’ denotes the safe place. In this grid there are also given some characters (E-Z) which occur more than one and donates if one reaches a tunnel he can go any other tunnel of same character and also any adjacent cell(8-directions). They also can move any adjacent cell from ordinary place. Each move takes 1 unit of time. Is it possible to go all of them to safe places??  If possible then what is the minimum time required.

Input:

Input starts with an integer T (≤ 15), denoting the number of test cases.

Each case starts with a line containing two positive integers H and W; W and H are the numbers of cells in the x and y directions, respectively. W and H are not more than 20.There will be H more lines in the data set, each of which includes W characters. Each character represents the status of a cell as follows.

1) '.' – ordinary place.

2) '#' – safe place

3) 'A', 'B','C' - initial position of Hippo and his friends.

4) 'D' – Dangerous place.

3) 'E-Z' - denote the tunnel.

Output:

For each test case, print the case number and minimum time if it is not possibleto reach all of them into safe position otherwise print “impossible” without quote.

Sample: