有一个网格,由 $$$2$$$ 行和 $$$n$$$ 列组成。网格的每个单元格要么空闲,要么被阻塞。
如果至少满足以下条件之一,则可以从空闲单元格 $$$x$$$ 访问空闲单元格 $$$y$$$:
- $$$x$$$ 和 $$$y$$$ 共享一边;
- 存在一个空闲单元$$$z$$$,使得$$$z$$$可以从$$$x$$$到达并且$$$y$$$可以从$$$z$$$到达。
连接区域是网格的一组空闲单元,其中的所有单元都可以相互访问,但向该组添加任何其他空闲单元会违反此规则。
例如,考虑以下布局,其中白色单元格空闲,深灰色单元格被阻挡:
其中有$$$3$$$区域,分别用红、绿、蓝色表示:
给定网格最多包含 $$$1$$$ 连接区域。您的任务是计算满足以下约束的空闲单元的数量:
- 如果此单元格被阻挡,则连接区域的数量恰好变为$$$3$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 列数。
接下来两行的第 $$$i$$$ 包含网格第 $$$i$$$ 行的描述 — 字符串 $$$s_i$$$,由 $$$n$$$ 字符组成。每个字符都是 . (表示空闲单元)或 x(表示阻塞单元)。
输入的附加约束:
- 给定网格最多包含 $$$1$$$ 连接区域;
- 所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 单元格数量,如果该单元格被阻塞,则连接区域的数量将变为 $$$3$$$。
示例
输入 #1
4 8 .......x .x.xx... 2 .. .. 3 xxx xxx 9 ..x.x.x.x x.......x
输出 #1
1 0 0 2
注意
在第一个测试用例中,如果单元格 $$$(1, 3)$$$ 被阻塞,则连接区域的数量变为 $$$3$$$ (如语句中的图片所示)。