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.

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 ≤ T ≤ 10
1 ≤ N ≤ 1000

 

Example
Input:
2
3
#..
#..
#..
3
#.#
#.#
#.#

Output:
6
0

Explanation
Example case 1. All places where rock are not there are valid positions.
Example case 2. No valid positions.

Note: Large input data. Use fast input/output.
Time limit for PYTH and PYTH 3.1.2 has been set 8s.
testcase = input()

while testcase:
    size = input()
    a = []
    for i in range(size):
        a.extend(map(list,raw_input().split()))
    
    col = set([])
    count = 0
    for i in range(size-1,-1,-1):
        blocked_row = False
        for j in range(size-1,-1,-1):
            if a[i][j] == '#':
                col.add(j)
                blocked_row = True
            if j not in col and not blocked_row:
                count += 1
    print count
    testcase -=1