7312: CodeChef GRID - Sherlock and the Grid
[Creator : ]
Description
Sherlock is stuck. There is a N X N grid in which some cells are empty (denoted by ‘.’), while some cells have rocks in them (denoted by ‘#’). Sherlock is on the South of the grid. He has to watch what is happening on the East of the grid. He can place a mirror at 45 degrees on an empty cell in the grid, so that he'll see what is happening on East side by reflection from the mirror.
But, if there's a rock in his line of sight, he won't be able to see what's happening on East side. For example, following image shows all possible cells in which he can place the mirror.
You have to tell Sherlock in how many possible cells he can place the mirror and see what's happening on East side.
But, if there's a rock in his line of sight, he won't be able to see what's happening on East side. For example, following image shows all possible cells in which he can place the mirror.
You have to tell Sherlock in how many possible cells he can place the mirror and see what's happening on East side.
Input
First line, T, the number of testcases. Each testcase will consist of N in one line. Next N lines each contain N characters.
Output
For each testcase, print the number of possible options where mirror can be placed to see on the East side.
Constraints
$1 \leq T \leq 10$
$1 \leq N \leq 1,000$
$1 \leq N \leq 1,000$
Sample 1 Input
2
3
#..
#..
#..
3
#.#
#.#
#.#
Sample 1 Output
6
0
Example case 1. All places where rock are not there are valid positions.
Example case 2. No valid positions.
Example case 2. No valid positions.