SP26705 PATHGAME - Path Game

猫咪 Snuke 正在玩一种叫做路径游戏的小游戏。 这个游戏是在一个由正方形小格子组成的矩形网格上进行的。网格有 2 行，并有若干列（为正整数）。每个格子要么是黑色，要么是白色。 从左到右的路径由一系列的白色格子组成。路径的起点在最左边的列，终点在最右边的列，相邻的两个格子必须共用一条边。 游戏开始时的网格着色方案，保证了至少存在一条从左到右的路径。我们用二维字符串表示初始着色方案。对于每个 $i$ 和 $j$，`grid[i][j]` 的符号要么是 `#`（代表黑色单元格），要么是 `.`（代表白色单元格）。 Snuke 可以将一些白色格子涂成黑色，但在涂色后，网格内至少还要保持一条从左到右的路径可通行。游戏的目标是尽可能多地将白色格子涂成黑色。请计算并返回 Snuke 最多可以涂黑多少个单元格。（注意，已经是黑色的格子不算在内。）

输入的第一行为整数 $T$，表示测试用例的数量。 接下来每个测试用例有如下输入格式： - 一行整数 $N$，表示网格的列数。 - 接下来的两行，每行为一个长度为 $N$ 的字符串，表示网格的初始着色方案。字符串的第 $j$ 个字符代表第 $i$ 行，第 $j$ 列的格子颜色。

对于每个测试用例，输出一个数字，表示Snuke最大可以涂黑的单元格数量。

- $1 \le T \le 100$ - $1 \le N \le 100$ **本翻译由 AI 自动生成**