CareerCup

Little Chandan is a friend everyone feels lucky to have. He is a happy-go-lucky-fellow and makes sure that everyone around him is happy. But recently, he came to know that his friend little Arjit is in serious trouble, and needs help. Like the great friend little Chandan is, he took the challenge upon himself without any serious thought, to make sure that little Arjit feels fine.

Now, little Arjit explains the story of his problems (His life, in general!) to let little Chandan figure out his troubles. After all, everyone needs help. All little Arjit needs is to get an internship somewhere, and complete his dual degree course, somehow, anyhow.

Little Chandan being the great genius man with psychic power decides to enter the brain of his friend to help him out.

Here are the contents of little Arjit's brain:
- His goals. (Internship, dual degree, remember?) - what Chandan needs to free. - Predictable empty spaces in his brain - plain empty spaces. - Ex-girlfriends and their memories - which CANNOT be penetrated, while traversing. - Windows which lead to the goal - which need to be open for little Chandan to pass.

Little Chandan knows the location of the two goals in his brain, the problem is while traveling through the path of his brain he'll have to break down the windows - once he has opened a window to cross that path, it remains open forever. So, he wants to minimize the number of windows he opens inside his friend's mind.

Help him plan his path accordingly, so he ends up breaking the minimum number of windows!

Input Format:
- First line contains a number t, denoting the number of test cases.
- Every test case will have the following:
- One line with two integers hm, wm - determining the width of the brain and the height of the brain.

The following characters define the state:
- X is the space which cannot be penetrated filled by the memories of ex-girlfriends. - W is the windows which little Chandan need to cross to reach the goal. - . is an empty space in the brain. - G are the two goals to be rescued.

Output Format:
1. Minimum number of windows Chandan needs to open to get to both the goals in Arjit's mind.

Constraints:
1 <= t <= 100
2 <= hm, wm <= 100

There are EXACTLY two goals in his mind.
For each goal, a path from the outside to that goal is surely going to exist.
Chandan can move around freely outside the mind.



Sample Input
1
5 9
XXXXWXXXX
X..W.W..X
XXXX.XXXX
XGW.W.WGX
XXXXXXXXX

Sample Output
4