Frogger

Philip J. Frog just wanted to take a mid-afternoon swim, but — being a frog — he has ended up in the middle of a busy street. Help Phil work out how long he will be hopping on the hot asphalt before he reaches the cool water.

Each second, Phil may hop one cell up, down, left, or right, or he may stay where he is. He may only move onto road, grass, or water cells, never onto a tree, and he may never occupy a cell that a car is on.

Phil and the cars move at the same time, so Phil can "hop over" an oncoming car (two of them swapping cells is not a collision). All that matters is that the cell Phil lands on is not occupied by a car at that same moment.

All horizontal movement wraps around: hopping right from the rightmost column lands Phil in the leftmost column. Vertical movement does not wrap.

Cars move one cell per second in the direction shown on the map (< = left, > = right), wrapping around, and never collide with anything.

The first line contains a single integer: the number of maps. Each map begins with two integers $R$ and $C$ ($0 < R, C \le 30$), the number of rows and columns, followed by $R$ lines of $C$ characters each describing the map. The possible characters are:

• Phil (&) — Phil's starting cell. Exactly one per map; the cell underneath is always road.
• Tree (T) — impassable.
• Grass (.) — Phil moves freely here.
• Road (-) — hot!
• Car (<, >) — the cell underneath is always road.
• Water (~) — Phil's goal.

For each map, output on its own line the minimum number of seconds Phil must spend standing on road cells in order to reach the water. Phil starts on a road cell, so that first second counts. If no sequence of moves ever brings Phil to the water, output Impassable instead.