Álvaro 和 José 是竞选 Tepito 总统职位的唯一候选人,Tepito 是一个由 $$$2$$$ 行和 $$$n$$$ 列组成的矩形网格,其中每个单元格代表一座房子。保证 $$$n$$$ 是 $$$3$$$ 的倍数。
在 Tepito 的投票系统下,网格将被分为多个区域,其中包含任何 $$$3$$$ 连接 $$$^{\text{*}}$$$ 的房屋。每栋房屋都属于一个地区。
每个区将投一票。如果该地区至少 $$$2$$$ 的房屋选择了阿尔瓦罗或何塞,则该地区将分别投票给他们。因此,总共将投出 $$$\frac{2n}{3}$$$ 票。
由于阿尔瓦罗是现任总统,他确切地知道各议院将选择哪位候选人。如果阿尔瓦罗将各议院最佳地划分为区,则确定他可以获得的最大票数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$($$$3 \le n \le 10^5$$$;$$$n$$$ 是 $$$3$$$ 的倍数)——Tepito 的列数。
以下两行每行包含一个长度为 $$$n$$$ 的字符串。第 $$$i$$$ 行包含字符串 $$$s_i$$$,由字符 $$$\texttt{A}$$$ 和 $$$\texttt{J}$$$ 组成。如果 $$$s_{i,j}=\texttt{A}$$$,则第 $$$i$$$ 行、第 $$$j$$$ 列的房子将选择 Álvaro。否则,如果 $$$s_{i,j}=\texttt{J}$$$,则众议院将选择 José。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出一个整数 - Álvaro 通过最佳地将房屋划分为多个区域可以赢得的最大区域数量。
示例
输入 #1
4 3 AAA AJJ 6 JAJAJJ JJAJAJ 6 AJJJAJ AJJAAA 9 AJJJJAJAJ JAAJJJJJA
输出 #1
2 2 3 2
注意
下图展示了 Álvaro 可用于示例中每个测试用例的区域的最佳排列。