// uva 11552 Fewest Flops

//

// 二维线性dp

//

// 首先，在该块必须是相同的来信。首先记录每块有很多种书

// 称为是counts[i];

//

// 订购f[i][j]它代表前i字母j为结尾的最小分块数

//

// 假设第i块的開始字母与第i-1块的结束字母同样

// f[i][j] = min(f[i][j],f[i-1][k] + counts[i] - 1);

//

// 否则

//

// f[i][j] = min(f[i][j],f[i-1][k] + counts[i]);

//

// 第一种情况的開始和结束字母同样有个前提：

// f[i-1][k]中的k在第i块中出现

//

// 之后的条件是：

// 1)第i块仅仅有一种字符

// 2)第i块结束字符与第i-1块结束字符不同样

//

// ps：第一种情况是另外一种情况的特殊，由于每种字母要么是在開始，

// 要么是在结束，不会连续的两个块结束字母同样，这样肯定不是

// 最优的，而假设第i块仅仅有一种字符。那么显然不在这之列。

//

// wrong answer了10次。如此顽强我也是醉了

//

// 继续练吧

#include <algorithm>

#include <bitset>

#include <cassert>

#include <cctype>

#include <cfloat>

#include <climits>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <functional>

#include <iostream>

#include <list>

#include <map>

#include <numeric>

#include <queue>

#include <set>

#include <stack>

#include <vector>

#define ceil(a,b) (((a)+(b)-1)/(b))

#define endl '\n'

#define gcd __gcd

#define highBit(x) (1ULL<<(63-__builtin_clzll(x)))

#define popCount __builtin_popcountll

typedef long long ll;

using namespace std;

const int MOD = 1000000007;

const long double PI = acos(-1.L);

const int maxn = 1008;

const int inf = 0x3f3f3f3f;

char s[maxn];

bool vis[maxn][30];

int f[maxn][300];

int n,k;

int counts[maxn];

void dp(){

	for (int i=0;i<=26;i++){

		if (vis[1][i]){

			f[1][i] = counts[1];

		}

	}

	for (int i=2;i<=n/k;i++){

		for (int j=0;j<26;j++){

			if (vis[i][j]){

				for (int m=0;m<26;m++){

					if (vis[i][m] && (counts[i]==1 || j!=m)){

						f[i][j] = min(f[i][j],f[i-1][m] + counts[i] - 1);

					}else{

						f[i][j] = min(f[i][j],f[i-1][m] + counts[i]);

					}

				}

			}

		}

	}

	int ans = inf;

	for (int i=0;i<26;i++){

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

	}

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

}

void print(){

	for (int i=1;i<=n/k;i++){

		cout << counts[i] << " ";

	}

	cout << endl;

}

void init(){

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

	n = strlen(s+1);

	memset(vis,0,sizeof(vis));

	memset(f,inf,sizeof(f));

	memset(counts,0,sizeof(counts));

	int x=1;

	for (int i=1;i<=n;i++){

		if (!vis[x][s[i]-'a']){

			counts[x]++;

			vis[x][s[i]-'a'] = 1;

		}

		if (i%k==0){

			x++;

		}

	}

//	cout << "x = " << x << endl;

//	print();

	dp();

}

int main() {

	int t;

	//freopen("E:\\Code\\1.txt","r",stdin);

	scanf("%d",&t);

	while(t--){

		init();

	}

	return 0;

}