Unique Paths with Obstacles

You are given a square grid of size \(n \times n\). Each cell in the grid contains either a 0 or a 1. A cell with 0 is empty, and a cell with 1 represents an obstacle. You start at the top-left cell (\(0,0\)) and aim to reach the bottom-right cell (\(n-1,n-1\)). You can only move either right or down.

The number of unique paths can be computed using dynamic programming with the recurrence relation:

[ \text{dp}[i][j] = \text{dp}[i-1][j] + \text{dp}[i][j-1]]

subject to the conditions that if a cell has an obstacle, no path goes through it, and if either the start or the destination is blocked then the answer is 0.

Your task is to compute the number of unique paths for each test case.

inputFormat

The first line of input contains an integer \(T\) \( (1 \leq T \leq 100) \) representing the number of test cases. For each test case, the first line contains an integer \(n\) \( (1 \leq n \leq 100) \) denoting the dimension of the grid (the grid is \(n \times n\)). This is followed by \(n\) lines, each containing \(n\) space-separated integers (either 0 or 1), where 0 indicates an empty cell and 1 indicates an obstacle.

The starting cell is the top-left cell and the destination is the bottom-right cell.

outputFormat

For each test case, output a single integer – the number of unique paths from the top-left cell to the bottom-right cell. Each answer should be printed on a new line.

## sample

1
3
0 0 0
0 1 0
0 0 0

2

</p>