### Problem

A common way to uniquely encode a string is by replacing its consecutive repeating characters (or “chunks”) by the number of times the character occurs followed by the character itself. For example, the string “aabbbaabaaaa” may be encoded as “2a3b2a1b4a”. (Note for this problem even a single character “b” is replaced by “1b”.)

Suppose we have a string S and a number k such that k divides the length of S. Let S1 be the substring of S from 1 to k, S2 be the substring of S from k + 1 to 2k, and so on. We wish to rearrange the characters of each block Si independently so that the concatenation of those permutations S ′ has as few chunks of the same character as possible. Output the fewest number of chunks.

For example, let S be “uuvuwwuv” and k be 4. Then S1 is “uuvu” and has three chunks, but may be rearranged to “uuuv” which has two chunks. Similarly, S2 may be rearranged to “vuww”. Then S ′ , or S1S2, is “uuuvvuww” which is 4 chunks, indeed the minimum number of chunks.

### Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1024, inf = 0x3f3f3f3f;
vector<int> has[maxn];
int T, len, n, k, v[maxn][30], dp[maxn][30];
char s[maxn];

void init() {
scanf("%d %s", &n, s);
len = strlen(s);
k = len / n;
for(int i = 0; i < k; ++i) {
has[i].clear();
memset(v[i], false, sizeof(v[i]));
for(int j = 0; j < n; ++j)
v[i][s[i*n+j]-'a'] = true;
for(int j = 0; j < 26; ++j)
if(v[i][j])
has[i].push_back(j);
}
memset(dp, -1, sizeof(dp));
}

int solve(int pos, int ed) {
if(pos < 0) return 0;
int & ans = dp[pos][ed];
if(ans != -1) return ans;
if(!v[pos][ed]) return ans = inf;
if(pos == 0) return ans = has[0].size();
ans = inf;
for(auto & i : has[pos-1]) {
int pre = solve(pos-1, i);
if(!v[pos][i]) {
ans = min(ans, pre + (int)has[pos].size());
} else {
if(i == ed && has[pos].size() == 1) ans = min(ans, pre);
else if(i == ed) ans = min(ans, pre + (int)has[pos].size());
else ans = min(ans, pre + (int)has[pos].size()-1);
}
}
return ans;
}

int main() {
scanf("%d", &T);
while(T--) {
init();
int ans = inf;
for(auto i : has[k-1])
ans = min(ans, solve(k-1, i));
printf("%d\n", ans);
}
return 0;
}