可能是爆栈了，但是按照道理应该不会爆栈，所以就很奇妙。（把 N 开成 6005 会 MLE）

#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int T, n, lcp[N][N], dp[N][N];
char s[N];
int dfs(int l, int r) {
	if(l > n) return 0;
	if(dp[l][r]) return dp[l][r];
	dp[l][r] = 1;
	if(r < n) dp[l][r] = max(dp[l][r], dfs(l, r + 1) + 1);
	else {
		for(int i = l + 1; i <= n; i++) {
			if(i + lcp[l][i] <= n && s[l + lcp[l][i]] < s[i + lcp[l][i]])
				dp[l][r] = max(dp[l][r], dfs(i, i + lcp[l][i]) + 1);
		}
	}
	return dp[l][r];
}

int main() {
//	freopen("1.in", "r", stdin);
	scanf("%d", &T);
	while(T--) {
		scanf("%d%s", &n, s + 1);
		for(int i = 1; i <= n + 1; i++)
			for(int j = i; j <= n + 1; j++)
				lcp[i][j] = dp[i][j] = 0;
		for(int i = n; i >= 1; i--)
			for(int j = n; j >= 1; j--) {
				if(i == j) {
					lcp[i][j] = n - i + 1;
				} else if(s[i] != s[j]) {
					lcp[i][j] = 0;
				} else {
					lcp[i][j] = lcp[i + 1][j + 1] + 1;
				}
			}
		int ans = 0;
		for(int i = 1; i <= n; i++)
			for(int j = i; j <= n; j++) 
				ans = max(ans, dfs(i, j));
		printf("%d\n", ans);
	}
	return 0;
}