## QUEEN - Wandering Queen

There is a checkmates board with n rows and m columns. Some of the cells of the board are occupied. There is a queen standing on a certain cell. It wants to move to another cell of this board. Help it do this making the least possible moves. The queen can go any number of cells in any of eight directions in a single move, but it can't pass through or stand on the occupied cells and leave the board.

### Input

The first line of the input contains number t – the amount of tests. Then t test descriptions follow. The first line of each test consists of two numbers n and m separated with a space. Then n lines follow each containing m characters describing the board. Character ‘.’ means a free cell, character ‘X’ – an occupied cell, character ‘S’ – the starting cell of the queen, character ‘F’ – the cell where the queen wants to go. It is guaranteed that there will be exactly one character ‘S’ and one character ‘F’ on each board.

### Constraints

1 <= t <= 30
2 <= n, m <= 1000

### Output

For each test case print the minimum number of moves the queen has to do to reach the desired cell. Print ‘-1’ if the queen can’t reach the cell.

### Example

```Input:
3
3 3
S..
...
..F
3 3
S..
XX.
F..
3 3
S..
XXX
..F

Output:
1
3
-1
```

hide comments
 yead_025: 2018-04-28 09:01:47 nice problem ! ducky94tb: 2018-01-15 04:15:44 Finally got accepted Last edit: 2018-12-31 03:53:06 vanamala: 2017-12-10 14:11:06 @SPOJ awesome work These problems are helping me to learn a lot ashish1508: 2017-07-08 11:16:43 getting all given test cases right ...but getting WA plz suggest some tricky test cases... holmesherlock: 2017-05-22 21:43:00 simple bfs is not helping ,,did some optimisations ,,stiil not passing devbishnoi: 2017-02-19 11:32:31 Accepted with 0.30 sec just optimise bfs approach Mine 99'th problem on spoj Last edit: 2017-02-19 11:34:57 Christoph Dürr: 2016-10-14 23:29:34 Please Spooky, the timelimit you give is too harsh. mr_bee: 2016-07-24 18:01:31 Time limit is very strict. BFS already a optimization algorithm. What do you want to do exactly in here? psrivast7788: 2016-04-26 15:33:53 Last edit: 2016-04-26 15:34:03 Abhishek K Das: 2014-10-28 06:45:15 Similar to the problem : spoj.com/problems/MLASERP

 Added by: Spooky Date: 2009-04-16 Time limit: 0.703s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ERL JS-RHINO NODEJS PERL6 VB.NET Resource: Advancement Spring 2009, http://sevolymp.uuuq.com/