Fry is the charge of a tomb raiders family. One day he found a ancient tomb.

The tomb is a n*n matrix,Fry had already known the treasure's position.But when he step into the tomb, he found something was wrong. There is some monsters in the tomb. In normal, Fry cost 1 hp to move to the nearby place, and as the charge of a tomb raiders, if there is just one monster in the tomb, Fry could ignore it.But if there is more than one monster in the tomb,they will add the cost of any move to be the same to the number of monster. Fry can kill the monster if he move to the same grid of one master. Besides, there is obstacles in the tomb, which means Fry could not step into this grid.

Now Fry is at (1,1) of matrix, what is the minimum hp Fry cost to get the treasure?

There is a T at the begining of file, show that there is T case follow.

For every case, first line is a integer n, mean the size of the tomb, from 2nd to the (n+1)th line, each line contain n char, mean the whole tomb.

'.'for empty space ,'M' for monster, 'B' for obstacles, and 'D' for treasure.

2<=n<=10, and there is no more than 4 moster in the tomb.

You can assure that (1,1) is empty space.

For every case, first output"Case #x: ",x mean the number of case.

If Fry can get the treasure, output the least hp he will cost, otherwise output"Impossible".

See sample for detail.