What is an astragalus nitififlorus?
What does it have?

Context

For about 100 years, astragalus nitidiflorus, also known as the garbancillo of Tallante, was thought to be an extinct plant species. However in 2004 it was rediscovered in a small hamlet of Cartagena called Tallante. This fact caused a great joy among biologists, botanists and local people, who celebrated the discovery with a party and a famous youtube video dedicated to the astragalus nitidiflorus.

The Problem

In this problem, you have to help biologists look for the plants of astragalus nitidiflorus. They have made a map of all the possible locations of this elusive plant species. The map takes the form of a matrix of characters. The plants can be located in the intersections of one vertical occurrence of the word "ASTRAGALUS" and one horizontal occurrence of the word "GARBANCILLOS".

For example, in the following map there is one possible location of the plant at the 6th row and 6th column:

We have used "." in order to improve visualization, but it could be replaced by any character. The occurrences of "GARBANCILLOS" are always from left to right, and "ASTRAGALUS" from up to down.

Each occurrence of "ASTRAGALUS" or "GARBANCILLOS" can only be used once at most. So, for example, in the following map there are four intersections but only one possible location of the plant:

.................
....GARBANCILLOS.
.....S...........
.....T...........
.....R...........
.GARBANCILLOS....
.....GARBANCILLOS
.GARBANCILLOS....
.....L...........
.....U...........
.....S...........

Write a program that, given a map, computes the maximum number of possible locations of astragalus nitidiflorus.

The Input

The input consists of a series of test cases. The first line contains a number that indicates the number of test cases.

Each case begins with two numbers, R, C, indicating the number of rows and columns of the map, respectively. Both numbers will be between 1 and 150. Then, there are R lines each with C characters, representing the map.

The Output

For each test case, you have to output the maximum possible locations of the plant; that is, the maximum number of intersections of a vertical "ASTRAGALUS" and a horizontal "GARBANCILLOS", where these occurrences cannot be used more than once.

Sample Input

2
11 14
..............
.....A........
.....S........
.....T........
.....R........
.GARBANCILLOS.
.....G........
.....A........
.....L........
.....U........
.....S........
13 23
GARBANCILLOS.......A...
A..........A.......S...
S..........S.......T...
T..........T..A....R...
R..........R..S....A...
A..........A..T....G...
G..........G..R....A...
A.........GARBANCILLOS.
L..........L..G....U...
U..........U..A....S...
GARBANCILLOS..L........
..............U........
...GARBANCILLOS........

Sample Output

1
3

OMP'15
Facultad de Informática
Universidad de Murcia