Unique Grid Paths

You are given a square grid of size \( n \times n \) where each cell is either open ('.') or blocked ('#'). Your task is to determine the number of unique paths from the top-left corner (starting intersection) to the bottom-right corner (destination intersection) such that you only move either down or right at any step and you avoid cells with traffic jams (marked by '#').

In other words, if you denote the cell in the \( i^{th} \) row and \( j^{th} \) column by \( grid[i][j] \), you may move from \( grid[i][j] \) to \( grid[i+1][j] \) or \( grid[i][j+1] \), provided that the destination cell is not blocked. The recurrence for the dynamic programming solution is given by:

[ \text{dp}[i][j] = \begin{cases} 0, & \text{if } grid[i][j] = '#' \ \text{dp}[i-1][j] + \text{dp}[i][j-1], & \text{otherwise} \end{cases} ]

Remember also that if the starting or ending cell is blocked, then the answer is \( 0 \).

inputFormat

The input is read from standard input (stdin) and has the following format:

T
n
row1
row2
... 
rown
(repeated for T test cases)

</p>

Where:

• T is the number of test cases.
• n is the size of the grid (the grid is \( n \times n \)).
• Each of the next n lines contains a string of length n consisting of the characters '.' and '#' representing open intersections and traffic jams respectively.

outputFormat

For each test case, output a single integer on a new line representing the number of unique paths from the starting cell at the top-left to the destination cell at the bottom-right.

## sample

3
3
...
.#.
...
3
.#.
##.
...
3
...
###
...

2
0
0

</p>