“Stop War, Save Life” - a life-changing motto proposed by the “Peace Want Society”.
The head of this society named Mr. Savior wants to establish this motto all over the world. He takes the responsibility. The evil guys set up a challenge for Mr. Savior. Those evil guys provide a map. The map is actually a grid. Each of the cells is either empty or contains an obstacle. Some of the obstacles are made of sands and some of them are made of concrete. Obstacles made of sands can easily be breakable whereas obstacles made of concrete cannot be breakable. Those evil guys throw Mr. Savior in an empty cell within the grid. He has to get out from that grid in order to save the war affected people. Mr. Savior can move towards left, right, top, bottom from the current cell.
He asked you to figure out minimum number of obstacles made by sands he needs to break in order to get out from the grid or determine if it is impossible.
Input
Inputs start with an integer T denotes the number of test cases you have to perform.
Each test case consists of two integers N, M that denotes the size of the grid. Each of the next N lines contains M characters. There are 4 types of characters -
‘ . ‘ – an empty cell.
‘#’ – Obstacle made of sands.
‘*’ – Obstacle made of concrete.
'$' - The location where the evil guys throw Mr. Savior. This symbol will present in the grid exactly once.
Constraints
1 ≤ T ≤ 5000
1 ≤ M,N ≤ 100
Output
For each test case, you need figure out the minimum number of obstacles made by sands he needs to break in order to get out from the grid or report him it’s impossible. If it is impossible you have to print “Impossible”.
Printing format will be “Case X: Y” where X is the case number and Y is the desired result. See samples for further clarification.
Sample
| Input | Output |
|---|---|
1 5 5 *.*** *#*.* *.$.* *.*#* ***.* | Case 1: 1 |
