#include <iostream>

#include <cstdio>

#include <cstring>

#define INF 1<<30

char ch[];

int rec[];

int f[][];

int vis[][];

int k;

int min(int a,int b)

{

    if (a<b) return a;

    return b;

}

int main()

{

    int t;

    scanf("%d",&t);

    while (t--)

    {

        scanf("%d %s",&k,ch);

        int len=strlen(ch);

        memset(rec,,sizeof rec);

        memset(vis,,sizeof vis);

        memset(f,,sizeof f);

        for (int i=;i<len/k;i++)

        {

            for (int j=;j<k;j++)

            {

                f[i][j]=INF;

            }

            for (int j=i*k;j<(i+)*k;j++)

            {

                vis[i][ch[j]]++;

            }

            for (int j='a';j<='z';j++)

            {

                if (vis[i][j])

                    rec[i]++; //计算chunks

            }

        }

        for (int i=;i<k;i++)

        {

            f[][i]=rec[]; //预处理第0位

        }

        for (int i=;i<len/k;i++)

        {

            for (int j=;j<k;j++)

            {

                for (int w=;w<k;w++)

                {

                    int rear=i*k+j;

                    int pre=(i-)*k+w;

                    if (vis[i][ch[pre]] &&(rec[i]== || ch[pre]!=ch[rear])) //如果第i位有第i-1位的该字母，则，除非第i位的chuanks=1，否则就必须第i位的最后一位不为该字母(该字母要放在序列头，则满足该条件)

                    {

                        f[i][j]=min(f[i][j],f[i-][w]+rec[i]-);

                    }

                    else

                    {

                        f[i][j]=min(f[i][j],f[i-][w]+rec[i]);

                    }

                }

            }

        }

        int ans=INF;

        for (int i=;i<k;i++)

        {

            ans=min(ans,f[len/k-][i]);

        }

        printf("%d\n",ans);

    }

    return ;

}