关键发现：超过长度2的子串一定可以分割成1、2长度的相邻块。

由此，$dp$ 定义为：dp[i][k]处理完前i个字符，最后一次分割的是k长度，其中1 <= k <= 2。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

int T = 1;
const int N = 1e6 + 1;
int n;
string s;
int dp[N][3];//dp[i][k]处理完前i个字符，最后一次分割的是k长度，其中1 <= k <= 2

void Clear() {
	memset(dp, 0, sizeof(dp));
}

void Solve() {
	cin >> n >> s;
	s = " " + s;
	for (int i = 1; i <= n; i++) {
		//我当前只分割出一个(i)
		dp[i][1] = dp[i - 1][2] + 1;
		if (s[i] != s[i - 1]) dp[i][1] = max(dp[i][1], dp[i - 1][1] + 1);
		//分割出两个
		if (i > 1) {
			dp[i][2] = dp[i - 2][1] + 1;
			if (i > 3 && (s[i - 3] + s[i - 2]) == (s[i - 1] + s[i])) {
				dp[i][2] = max(dp[i][2], dp[i - 2][2] + 1);
			}
		}
	}
	cout << max(dp[n][1], dp[n][2]) << '\n';
	Clear();
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	while (T--) {
		Solve();
	}
	return 0;
}