NATALIAG - Natalia Plays a Game


When Natalia is not having fun studying Computing Science in Santiago de los Caballeros, she opens up her bag and pulls out an iPad she won at a Programming Olympiad to play a classical maze game.

The maze is a rectangular figure of M rows and N columns. Open areas are represented by a 'O' while closed areas are represented by a '*'. An area is just a 1x1 block inside the maze. There's an entrance area marked by a '$' and a destination area marked by a '#'. Please note that both the entrance and destination are also open areas. 

Once Natalia is located inside an open area, she can decide to move to either cardinal direction (north, south, east or west). In other words, if Natalia is located at (x,y), she can move to either (x + 1, y), (x - 1, y),  (x, y + 1) or (x, y - 1). Of course, she can't move inside a closed area.

Given a rectangular maze as described above, output the minimum number of steps necessary to reach the final position from the starting area, if it is possible. If not, output '-1'.

Input

The input contains many lines. The first line contains an integer T (1 ≤ T ≤ 100), the number of test cases. For each test case there's a first line that contains two space separated integers M and N (1 ≤ M ≤ 100), (2 ≤ N ≤ 100), the dimensions of the maze. The line is followed by M lines. Each of these lines contain a string of N characters. The position at index j of the ith string represents the marker of the i,j area. It can be either an open marker ('O'), a closed marker ('*'), the unique entrance marker ('$') or the unique destination marker ('#'). 

Output

For each test case output the minimum number of steps necessary to reach the final position from the entrance position. If it is impossible to reach the final position, output -1.

Example

Input:
2
$OO
2 3 3 $OO *** OO# 3 3 $*# O*O OOO
***
O#
3 3
$*#
O*O
OOO2 3 3 $OO *** OO# 3 3 $*# O*O
Output:

-1
6


hide comments
pigpork: 2018-09-29 07:40:09

#include <bits/stdc++.h>
using namespace std;
int main ( )
{
I am ded;
}

Last edit: 2018-09-29 08:00:10
nadstratosfer: 2017-10-06 18:10:05

Yeah, girl winning at Programming Olympiad, Cuck News would be all over it.. Unfortunately automated judges aren't influenced by stupid ideologies. Cool story bro, then again there's always https://encyclopediadramatica.rs/Golden_ipod to win.

vanvinhbk94: 2017-02-28 03:06:16

AC in one go

kushalanand: 2016-07-21 23:34:39

AC in one go. mohit pro thanks /\.

iharsh234: 2016-07-12 23:47:13

too easy!

poojan : 2016-05-14 06:26:28

AC after 2 WA!
Good que!

Anubhav Gupta: 2015-11-16 20:59:52

its not necessary that $ is at (0,0) in the matrix. costed me WA's

anshal dwivedi: 2015-07-31 11:52:33

AC in one go! simple bfs..

ankit kumar: 2015-07-02 10:58:14

http://ideone.com/AJFlyV
i m getting WA check the above code.

Priyanjit Dey: 2015-04-19 14:39:46

This one's really good.. a basic problem which must be solved before attempting any other path related problems. :)


Added by:kojak_
Date:2012-09-18
Time limit:0.566s-1.233s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Roberto Abreu's Repository