Background

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.

Problem

In this problem you are given the jungle-map as a 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 denotes 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.

• '.' – ordinary place.
• '#' – safe place.
• 'A', 'B', 'C' - initial position of Hippo and his friends.
• 'D' – Dangerous place.
• 'E' - 'Z' - denote the tunnel.

Output

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

Example

Input:
2
5 6
C..E#.
.D....
F..E..
.D..A.
.B.D.F
4 4
C.D#
.FDD
A..E
.B.F

Output:
Case 1: 4
Case 2: impossible

Problem Setter: Md Abdul Alim, Dept. of Computer Science, Bangladesh University of Business and Technology