sah

Time limit: 0.5s Memory limit: 64MB Input: Output:

Cerință

Credeați că scăpați fără o problemă cu șah? V-ați gândit prost!

Se dă o tablă de șah de dimensiuni obișnuite (88 linii și 88 coloane), în care piesele sunt notate cu * (steluță), iar spațiile libere sunt notate cu . (punct).

Pentru a-i învăța pe elevi cum trebuie să folosească regina la valoarea ei maximă, profesorul de șah le-a arătat elevilor diverse metode de a plasa regina pe tablă pe un spațiu liber pentru a ataca cât mai multe piese.

Acum ai primit temă să afli pentru diferite configurații numărul maxim de piese care pot fi atacate concomitent.

Regina se mișcă pe linie, coloană și ambele diagonale până ce fie dă de o piesă, fie dă de o margine a tablei.

Date de intrare

Pe prima linie se va afla tt, numărul de teste.

Pe următoarele 8t8 \cdot t linii se vor afla tablele de șah, unde piesele sunt notate cu * (steluță), iar spațiile libere sunt notate cu . (punct).

Date de ieșire

Pe fiecare din cele tt linii se va afla răspunsul căutat pentru testul respectiv.

Restricții și precizări

  • t100t \leq 100

Exemplu

stdin

2
**......
....*...
..*....*
*....*..
..*..*..
.....*..
...*..**
**......
.....*..
........
.....*..
..*.....
....*...
........
.*....*.
........

stdout

7
4

Explicație

Pentru primul test, plasarea reginei pe (2,1)(2, 1) ne permite să atacăm 44 piese.

Răspunsul optim este 77, prin plasarea reginei pe pătratul (5,5)(5, 5).

Log in or sign up to be able to send submissions!