Prison Break

Sanggeun has to break two prisoners out of a jail. The jail is a single-story building, and he just got hold of its floor plan.

The plan shows every wall and every door, and it also marks where the two prisoners are. The jail is unmanned, so those two are the only people inside.

Doors open from the central control room only. Sanggeun has a special technique that opens a door without going through the control room, but opening one door takes a very long time. A door he has opened stays open. Write a program that finds the smallest number of doors he has to open to get both prisoners out of the jail.

A person moves only to a cell directly above, below, left or right, and cannot pass through a wall. Everything outside the floor plan is open ground, so he walks around out there freely.

The first line has the number of test cases, which is at most 100.

The first line of each test case has the height h and the width w of the floor plan. (2 ≤ h, w ≤ 100) The next h lines give the plan, w characters per line. Empty space is ., a wall that cannot be crossed is *, a door is #, and a prisoner is $.

The plan always marks exactly two prisoners, and every input has a path from each prisoner to the outside of the jail.

For each test case, print on its own line the smallest number of doors that must be opened to break both prisoners out.