Counting Paths in a Grid

Given an \(n \times n\) grid, count the number of distinct ways to travel from the top-left cell to the bottom-right cell. You can only move right (\(\rightarrow\)) or down (\(\downarrow\)). Some cells may be impassable and are marked with a '#' character, while passable cells are marked with a '.'.

If either the starting cell (top-left) or the destination cell (bottom-right) is blocked, the answer is 0.

Solve this problem using dynamic programming.

inputFormat

The input is read from stdin. The first line contains an integer (T), the number of test cases. For each test case, the first line contains an integer (n) indicating the size of the grid (number of rows and columns). This is followed by (n) lines, each containing a string of length (n) composed of the characters '.' and '#' representing the grid.

outputFormat

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

3
4
....
.#..
..#.
....
3
.#.
##.
..#
2
..
..

4
0
2