一个区间一个区间的考虑，当前区间的决策只和上一次的末尾有关，考虑转移的时候先统计当前区间出现过的字母以及种数ct
枚举上一个区间的末尾标号j，规定小于INF为合法状态，确定j之后看j有没有在当前的区间出现，如果出现则贪心选块数+ct-1，
枚举当前的结尾。为了方便处理，增加一个0区间，初始为0，这样所有的块数会减1，转移完以后在加上1。
#include<bits/stdc++.h>
using namespace std; const int LEN = 1e3+;
int dp[LEN][];
char s[LEN];
const int INF = 0x3f3f3f3f;
//#define LOCAL
int main()
{
#ifdef LOCAL
freopen("in.txt","r",stdin);
#endif
int T; cin>>T;
//for(int i = 1; i < 26; i++) dp[0][i] = 1;
//memset(dp[0],0x3f,sizeof(dp[0]));
while(T--){
int k; scanf("%d%s",&k,s);
int len = strlen(s), mi = len/k;
for(int i = ; i <= mi; i++){
bool exs[] = {};
for(int j = (i-)*k; j < i*k; j++){
exs[s[j]-'a'] = true;
}
int ct = ;
for(int j = ; j < ; j++) ct += exs[j];
memset(dp[i],0x3f,sizeof(dp[i]));
for(int j = ; j < ; j++){
if(dp[i-][j]<INF){
if(exs[j]){
if(ct == ) { dp[i][j] = min(dp[i][j],dp[i-][j]); continue; }
for(int k = ; k < ; k++){
if(exs[k] && k != j){
dp[i][k] = min(dp[i][k],ct-+dp[i-][j]);
}
}
dp[i][j] = min(dp[i][j],ct+dp[i-][j]);
}else {
for(int k = ; k < ; k++){
if(exs[k]){
dp[i][k] = min(dp[i][k],ct+dp[i-][j]);
}
}
} }
}
}
int ans = INF;
for(int j = ; j < ; j++) ans = min(dp[mi][j],ans);
printf("%d\n",ans+);
}
return ;
}