发现如果只有一块就是种类的数目，也就是同种放在一起，
再考虑多块，如果违背的上面的规律，可以发现不会更优，
于是问题就是求在满足同种类放在一起的前提下，尽量使得相邻块的两端一模一样
然后dp一下就可以了
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define MAXN 1005
using namespace std;
int n,k;
char s[MAXN];
int b[MAXN][];
int len[MAXN];
int dp[MAXN][];
void solve(){
memset(dp,0x3f,sizeof(dp));
memset(b,,sizeof(b));
memset(len,,sizeof(len));
scanf("%d",&k);
scanf("%s",s);
n=strlen(s);
for(int i=;i<n;i+=k){
for(int j=i;j<=i+k-;j++){
if(!b[i/k][s[j]-]){
len[i/k]++;
}
b[i/k][s[j]-]=;
}
}
for(int i=;i<=;i++){
if(b[][i])
dp[][i]=len[];
}
for(int i=;i<n/k;i++){
for(int j=;j<=;j++){
if(b[i][j]){
for(int s=;s<=;s++){
if(b[i-][s]){
dp[i][j]=min(dp[i][j],dp[i-][s]-(b[i][s]&&(len[i]==||j!=s)));
}
}
dp[i][j]+=len[i];
}
}
}
int ans=0x7f7f7f7f;
for(int i=;i<=;i++){
ans=min(ans,dp[(n/k)-][i]);
}
printf("%d\n",ans);
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("my.out","w",stdout);
int T;
scanf("%d",&T);
while(T--){
solve();
}
return ;
}