C. 选区划分

时间限制：每个测试 $2$ 秒
内存限制：$256$ MB

我们都会偷一点。但我只有一只手，而我的对手有两只。
—— 阿尔瓦罗·奥布雷贡

阿尔瓦罗和何塞是特皮托总统选举中仅有的两位候选人。特皮托是一个 $2$ 行 $n$ 列的矩形网格，每个单元格代表一所房屋。保证 $n$ 是 $3$ 的倍数。

根据特皮托的投票制度，网格将被划分为若干个选区，每个选区由任意 $3$ 个连通*的房屋组成。每个房屋恰好属于一个选区。

每个选区投出一张选票。如果该选区中至少有 $2$ 个房屋选择了某位候选人，则该选区投票给该候选人。因此，总共将有 $\frac{2n}{3}$ 张选票被投出。

作为现任总统，阿尔瓦罗确切地知道每个房屋将选择哪位候选人。如果阿尔瓦罗最优地划分房屋为选区，请确定他能获得的最大票数。

*一组单元格是连通的，如果任意两个单元格之间可以通过仅向上、下、左、右移动经过该组中的单元格到达。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 10^5$，$n$ 是 $3$ 的倍数），表示特皮托的列数。

接下来的两行各包含一个长度为 $n$ 的字符串。第 $i$ 行包含字符串 $s_i$，由字符 A 和 J 组成。如果 $s_{i,j} = \text{A}$，则第 $i$ 行第 $j$ 列的房屋将选择阿尔瓦罗。否则如果 $s_{i,j} = \text{J}$，则选择何塞。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，输出一个整数——通过最优划分，阿尔瓦罗能赢得的最多选区数量。

示例

输入

4
3
AAA
AJJ
6
JAJAJJ
JJAJAJ
6
AJJJAJ
AJJAAA
9
AJJJJAJAJ
JAAJJJJJA

输出

2
2
3
2

样例解释

下图展示了阿尔瓦罗在每个测试用例中可以使用的选区最优划分方式。