University of Toronto ACM-ICPC Tryouts 2012

A family of Foxen, having caught a pesky farmer on their property, want to teach him a lesson. Of course, they're not cruel - they plan to simply prevent him from returning home to his farm, until he's willing to beg them for mercy.

The Foxen and the farmer live in a forest, which may be viewed as a grid of cells, with ~H~ ~(1 \le H \le 6)~ rows of ~W~ ~(1 \le W \le 6)~ cells each. Each cell contains either grass (represented by G), trees (T), the farmer (F), or his farm (H). The farmer may repeatedly move up, down, left, or right to adjacent cells within the grid, provided that they are not blocked by trees. Due to his overconfidence in exploring the forest, the farmer is not directly adjacent to his farm.

The family of Foxen can also block the farmer's way, by standing in grass-filled cells. He would not, of course, dare to enter a cell with a Fox in it. However, the Foxen do have better things to do, so they'd like to determine the minimum number of cells they must occupy in order to prevent the farmer from ever reaching his farm.

There are ~T~ ~(1 \le T \le 20)~ scenarios as described above. For each one, you'd like to answer the Foxen's question. Note that no Foxen might be necessary if the trees already bar the farmer's way sufficiently.

Input Specification

Line 1: 1 integer, ~T~
For each scenario:
Line 1: 2 integers, ~H~ and ~W~
Next ~H~ lines: ~W~ characters, representing the ~i~th row of the grid, for ~i = 1 \dots H~

Output Specification

For each scenario:
Line 1: 1 integer, the minimum number of Foxen necessary to block the farmer.

Sample Input

2
1 5
FGTGH
4 5
GGGGG
GFGTG
GTTGH
GGGGG

Sample Output

0
2

Explanation of Sample

In the first scenario, the farmer can already never reach his farm, so no Foxen are necessary.

In the second scenario, one possible placement of two Foxen (each represented by an X) is as follows:

GGGGX
GFGTG
GTTGH
GGXGG