#include <stdio.h>

 #include <string.h>

 #include <algorithm>

 using namespace std;

 int main()

 {

     int T;

     int k,numk;

     int i,j;

     char a[];

     int num[],q[][],dp[][];

     scanf("%d",&T);

     while(T--)

     {

         memset(num,,sizeof(num));

         memset(q,,sizeof(q));

         memset(dp,,sizeof(dp));

         scanf("%d",&k);

         scanf("%s",a);

         int l=strlen(a);

         numk=l/k;

         if(l%k!=)

             numk++;

         for(i=;i<=numk;i++)

         {

             for(j=(i-)*k;j<=i*k- && j<l;j++)

             {

                 int o=a[j]-'a'+;

                 if(q[i][o]==)

                 {

                     num[i]++;

                     q[i][o]=;

                 }

             }

         }

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

         {

             if(q[][i]==)

                 dp[][i]=num[];

         }

         for(i=;i<=numk;i++)

         {

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

             {

                 if(q[i][j]==)

                 {

                     if(q[i-][j]==)

                     {

                         dp[i][j]=dp[i-][j]+num[i];

                         if(num[i-]==)

                             dp[i][j]--;

                         else

                         {

                             for(int u=;u<=;u++)

                             {

                                 if(u!=j && q[i-][u]==)

                                     dp[i][j]=min(dp[i][j],dp[i-][u]+num[i]-);

                             }

                         }

                     }

                     else

                     {

                         dp[i][j]=;

                         for(int u=;u<=;u++)

                         {

                             if(q[i-][u]==)

                                 dp[i][j]=min(dp[i][j],dp[i-][u]+num[i]);

                         }

                     }

                 }

             }

         }

         int ans=;

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

         {

             if(q[numk][i]== && dp[numk][i]<ans)

                 ans=dp[numk][i];

         }

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

     }

     return ;

 }