网格路径

给定一张 $n\times n$ 的网格图，有些格子能走，有些格子不能走，左上角的格子坐标为 $(1,1)$，右下角的格子坐标为 $(n,n)$。

问最多可以找到多少条从 $(1,1)$ 到 $(n,n)$ 的不相交路径，使得每条路径经过的每个格子（包含 $(1, 1)$ 和 $(n, n)$）都是能走的格子？

每次我们只可以向右或向下走，不能离开网格图的边界。两条路径不相交当且仅当除了格子 $(1,1)$ 和 $(n,n)$，它们没有任何公共部分。

第一行一个整数 $test(1\leq test \leq 1000)$ 表示数据组数。

对于每组数据，第一行一个整数 $n(2\leq n \leq 10)$ 表示网格图的大小。

接下来 $n$ 行，每行一个长度为 $n$ 的字符串。第 $i$ 行第 $j$ 列的字符 '.' 表示 $(i,j)$ 可以走，'#' 表示不能走。

对于每组数据，输出一行一个整数表示最多可以找到的不相交路径数目。

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

2
1
0

2021 年百度之星·程序设计大赛 - 初赛三