题目描述

We all steal a little bit. But I have only one hand, while my adversaries have two.

Álvaro Obregón

Álvaro and José are the only candidates running for the presidency of Tepito, a rectangular grid of $2$ rows and $n$ columns, where each cell represents a house. It is guaranteed that $n$ is a multiple of $3$.

Under the voting system of Tepito, the grid will be split into districts, which consist of any $3$ houses that are connected$^{\text{∗}}$. Each house will belong to exactly one district.

Each district will cast a single vote. The district will vote for Álvaro or José respectively if at least $2$ houses in that district select them. Therefore, a total of $\frac{2n}{3}$ votes will be cast.

As Álvaro is the current president, he knows exactly which candidate each house will select. If Álvaro divides the houses into districts optimally, determine the maximum number of votes he can get.

$^{\text{∗}}$A set of cells is connected if there is a path between any $2$ cells that requires moving only up, down, left and right through cells in the set.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($3 \le n \le 10^5$; $n$ is a multiple of $3$) — the number of columns of Tepito.

The following two lines each contain a string of length $n$. The $i$-th line contains the string $s_i$, consisting of the characters $\texttt{A}$ and $\texttt{J}$. If $s_{i,j}=\texttt{A}$, the house in the $i$-th row and $j$-th column will select Álvaro. Otherwise if $s_{i,j}=\texttt{J}$, the house will select José.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output a single integer — the maximum number of districts Álvaro can win by optimally dividing the houses into districts.

Example
input

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

output

2
2
3
2

Note

The image below showcases the optimal arrangement of districts Álvaro can use for each test case in the example.

思路
采用dp
首先进行分析的话能发现

一共有这几种区块，我们可以用 0，1，2来表示最后平滑，上凸，下凸
$dp[i][0,1,2]$表示在第i列尾部是平滑或上凸或下凸的区块中最大得票数
然后就是顺水推舟的就能把转移方程写出来

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;

void solve() {
  int n;
  cin >> n;
  string s[3];
  cin >> s[0] >> s[1];
  s[0] = " " + s[0];
  s[1] = " " + s[1];

  auto check = [&](char a, char b, char c) {
    return (((a == 'A') + (b == 'A') + (c == 'A')) >= 2);
  };
  vector<vector<int>> dp(n + 2, vector<int>(4));
  for (int i = 1; i <= n; i++) {
    if (i + 3 < n) {
      dp[i + 3][1] =
          max(dp[i + 3][1],
              dp[i][1] + check(s[0][i + 1], s[0][i + 2], s[0][i + 3])) +
          check(s[1][i], s[1][i + 1], s[1][i + 2]);
      dp[i + 3][2] = max(dp[i + 3][2],
                         dp[i][2] + check(s[0][i], s[0][i + 1], s[0][i + 2])) +
                     check(s[1][i + 1], s[1][i + 2], s[1][i + 3]);
    }
    if (i + 2 <= n)
      dp[i + 2][0] =
          max(dp[i + 2][0], dp[i - 1][0] +
                                check(s[0][i], s[0][i + 1], s[0][i + 2]) +
                                check(s[1][i], s[1][i + 1], s[1][i + 2]));
    if (i + 1 <= n) {
      dp[i + 1][0] = max(dp[i + 1][0],
                         dp[i][1] + check(s[1][i], s[1][i + 1], s[0][i + 1]));
      dp[i + 1][0] = max(dp[i + 1][0],
                         dp[i][2] + check(s[0][i], s[1][i + 1], s[0][i + 1]));
    }
    if (i + 1 < n) {
      dp[i + 1][1] = max(dp[i + 1][1],
                         dp[i - 1][0] + check(s[0][i], s[0][i + 1], s[1][i]));
      dp[i + 1][2] = max(dp[i + 1][2],
                         dp[i - 1][0] + check(s[0][i], s[1][i], s[1][i + 1]));
    }
  }
  cout << dp[n][0] << "\n";
}

int main() {
  int _;
  cin >> _;
  while (_--) {
    solve();
  }
  return 0;
}