Un câmp de luptă a fost minat şi sarcina lui Gigel, căutător de mine specializat, este să demineze câmpul respectiv. Gigel a marcat câmpul de luptă, împărţindu-l în N linii şi N coloane. El a reuşit să determine unde sunt minele şi le-a marcat.
Pentru a demina terenul, el porneşte dintr-o poziţie iniţială cunoscută. Pentru a dezamorsa o mină el trebuie să se afle în poziţia minei respective.
Pentru a minimiza pericolul acţionării accidentale a unei mine, el vrea să încerce o nouă strategie, şi anume să parcurgă terenul, plecând din locul unde se află, deplasându-se numai spre dreapta şi făcând numai paşi de tipul mişcărilor calului pe tabla de şah (vezi figura), adică din poziţia (i,j), unde i reprezintă linia, iar j coloana, poate să ajungă doar în una dintre poziţiile (i-2,j+1), (i-1,j+2), (i+1,j+2), (i+2,j+1), fără a părăsi câmpul de luptă.
Cerinţă
Determinaţi numărul maxim de mine pe care Gigel le poate dezamorsa, plecând din poziţia sa iniţială.
Date de intrare
Prima linie a fişierului de intrare mine.in conţine o valoare naturală T, reprezentând numărul de cazuri de test. Apoi urmează cazurile de test. Fiecare caz de test are următoarea formă:
- prima linie conţine o valoare naturală N, reprezentând dimensiunea câmpului de luptă;
- apoi urmează N linii, fiecare linie conţinând N caractere, care pot fi ′.′, ′G′ sau ′M′. Caracterul ′.′ reprezintă o poziţie fără mină, caracterul ′M′ reprezintă o poziţie în care se află o mină, iar caracterul ′G′ poziţia iniţială a lui Gigel. Gigel lucrează singur, deci există un singur caracter ′G′ în datele de intrare. În poziţia iniţială a lui Gigel nu există mină.
Date de ieşire
În fişierul de ieşire mine.out se va afişa pentru fiecare caz de test o singură linie pe care se va găsi numărul maxim de mine dezamorsate în cazul respectiv.
Restricţii
1 ≤ T ≤ 5
4 ≤ N ≤ 1000
Exemple
mine.in
mine.out
Explicaţii
1
5
G....
..M..
.M...
...M.
.....
2
În fişierul de intrare există un singur caz de test.
Cele două mine dezamorsate de Gigel sunt: (3,2) şi (4,4) sau (2,3)şi (4,4)
