Some senior provincists recently get indulged with a game called A Tod.
The objective of the game is to control a single hero called Tod, raise Tod's level to the game's requirement, and then finally exit the map.
To raise a level, a hero has to pick up a gem "G" on the map. When a gem is picked up, the space does not have a gem any more. In other words, the gems do not have replacement. There are many trees "T" in the forest, and the hero cannot pass through them. The maps have 10 by 10 dimensions. "A" indicates the spawn position of the hero and "B" indicates the exit.
In this question, the requirement of the game is to pick up at least two gems.
The input starts with an integer n specifying the number of test cases. Then n maps follows. A map is represented by characters "ABGT.", where "." means a passage that the hero can pass without hindrance. The map is always 10 by 10. The graph is always valid, with no leading and trailing spaces, exactly one A and one B, and at least two gems are always accessible. There is a blank line between any two maps.
For each test case, print a single integer indicating the minimum number of steps that Tod needs to walk in order to exit after raising two levels.
3 TTTTTTTTTT T.G...G.BT T.T....G.T TGT...GTGT T..T.....T T........T TGTG..T.GT T.G......T TA..G..G.T TTTTTTTTTT TTTTTTTTTT T.G...G.BT TGT....G.T TGTTTTTTTT T..T.....T T.......GT TTTTTTTTGT T.G......T TA..G..G.T TTTTTTTTTT G........G .......... .......... .......... .......... ..AB...... .......... G........G .......... ..........
14 28 19