广受好评的全新奇幻动作角色扮演游戏《远古法杖》中的第一个地点是有毒沼泽。沼泽里长着一些睡莲。它可以表示为 $$$2 \times n$$$ 网格($$$2$$$ 行和 $$$n$$$ 列),其中每个单元格要么是空的,要么里面有一个睡莲叶。
沼泽中有 $$$n$$$ 睡莲叶 — 每列都有一个。每片睡莲叶上都栖息着一只青蛙。在一次移动中,每只青蛙必须跳到相邻的一个侧格。
移动后,任何青蛙都不能在网格之外,并且任何两只青蛙都不能共享同一片睡莲叶。相邻单元格中的两只青蛙不能跳向彼此(即交换单元格)。
如果青蛙跳到睡莲叶上,它就会活下来。否则,它就会掉进有毒的沼泽,并被生活在底部的可怕生物吞噬。
您可以选择每只青蛙跳跃的方向。确定一次移动后可以存活的最大青蛙数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 沼泽网格中的列数。
以下两行中的每一行都包含沼泽行的描述 - 一个字符串,由 $$$n$$$ 个字符组成。每个字符要么是一个点(“.”),表示沼泽单元,要么是一个星号(“*”),表示带有青蛙的睡莲叶。
在每一列中,只有一个点和一个星号。所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 如果您选择每只青蛙跳跃的方向,则一次移动后可以生存的青蛙的最大数量。
示例
输入 #1
3 5 *..** .**.. 1 * . 3 ... ***
输出 #1
2 0 2
注意
第 $$$i$$$ 青蛙是第 $$$i$$$ 列睡莲叶上的青蛙。
在第一个测试用例中:
- 第一只青蛙无法生存,因为没有相邻的睡莲叶;
- 第二只和第三只青蛙可以分别向右和向上跳——没有办法同时拯救它们;
- 第四只和第五只青蛙可以分别向左和向左跳——没有办法同时拯救它们;但请注意,第三只和第四只青蛙最终会出现在沼泽的同一个牢房中,这是不被禁止的。