题意：给一个正整数k和字符串s，s的长度是k的倍数，把s每k个字符分成一组，没组之间的字符可以任意重排，但组与组之间的顺序保持不变。

任务是让重排后的新字符串s'的块最少，连续相同的字符组成一个块,比如abbbaa有三个块a、bbb、aa。

 

首先每一组子串中相同的字符肯定要放在一起，然后问题就变成怎么排列这些子串中的块。

用dp[i][fa]表示前i组且第i+1组的最左边的字符是fa+'a'的状态能得到的最少的块数

那么状态的转移就是两层循环枚举这个第i组最左边和最右边应该放上什么字符，如果最右边和前一组的最左边一样，那么总块数就是加上（X-1)否则加上X，X表示这一组中字符的种类，也就是这一组中块的数量。

注意当一组中只有一种字符的特殊情况。

 

vector
      
        g[1010];int n;int dp[1010][27];int f(int k,int fa){    if(dp[k][fa]>=0)return dp[k][fa];    if(k==0)return 0;    vector
       
         &ans=g[k];    int minn=INF;    for(int i=0;i
        
         1?1:0));        }    }    return dp[k][fa]=minn;}int main(){    int t;    scanf("%d",&t);    for(int ca=1;ca<=t;ca++)    {        int k;        char s[1100];        scanf("%d%s",&k,s);        n=0;        for(int i=0;s[i]!='\0';i+=k)        {            char str[1100];            for(int j=i;j