#include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn =  + ;

 const int maxm = ;

 int n, k;

 char s[maxn];

 int d[maxn][maxm];

 int cnt[maxn];

 bool vis[maxn][maxm];

 int main()

 {

     int T; scanf("%d", &T);

     while(T--)

     {

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

         n = strlen(s);

         memset(d, 0x3f, sizeof(d));

         memset(cnt, , sizeof(cnt));

         memset(vis, false, sizeof(vis));

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

         {

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

             {

                 int ch = s[i + j] - 'a';

                 if(!vis[i][ch]) cnt[i]++;

                 vis[i][ch] = true;

             }

         }

         for(int i = ; i < ; i++) if(vis[][i]) d[][i] = cnt[];

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

             for(int j = ; j < ; j++) if(vis[i][j])

                 for(int t = ; t < ; t++) if(vis[i - k][t])

                 {

                     if(vis[i][t] && (j != t || cnt[i] == ))

                         d[i][j] = min(d[i][j], d[i-k][t] + cnt[i] - );

                     else

                         d[i][j] = min(d[i][j], d[i-k][t] + cnt[i]);

                 }

         int ans = n;

         for(int i = ; i < ; i++) ans = min(ans, d[n - k][i]);

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

     }

     return ;

 }