编程题：行走方案数

在一个$n × n$的方阵区域内，某些小方格内存在障碍物，小明在左上角的方格内，想走到右下角的方格内。若某方格内存在障碍物则不能走，且小明只能往下或往右走。请问从左上角方格$(0, 0)$ 走到右下角方格$(n-1, n-1)$ 总共有多少种走法？

例如，$4 × 4$ 的方阵区域如下图所示，左上角方格为$(0, 0)$，右下角为$(3, 3)$。从左上角方格到右下角方格共有10种走法。


### 输入格式:

首先输入一个正整数$T(T≤20)$，表示测试数据的组数。然后输入$T$组测试数据。对于每组测试，第一行输入一个整数$n(1<n≤20)$；接着输入$n$行，每行$n$个字符，其中，字符“.”表示该方格可以走，“#”表示该方格存在障碍物不能走。

### 输出格式:

对于每组测试，输出一个整数，表示从左上角方格走到右下角方格的走法总数（结果保证小于$2^{31}$）。

### 输入样例:

in
2
4
..#.
...#
#...
....
15
...#...........
..............#
...............
...............
...............
...............
...............
......#........
...............
...............
.....#......#..
...............
...............
#..............
...............



### 输出样例:

out
10
17029962








答案：若无答案欢迎评论