#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, M = 1e6 + 6, OO = 0x3f3f3f3f;
int tc;
int n;
string s;
int freq[26][131075];
int mem[131075][26];
int solve(int lo = 0, int hi = n - 1, int strc = 0) {
  if (lo > hi || strc > (n / 2)) return 0;
  if (mem[lo][strc] != -1) return mem[lo][strc];
  int mid = (hi + lo) / 2;
  int freqRight = freq[strc][hi] - freq[strc][mid];
  int freqLeft = freq[strc][mid] - (lo == 0 ? 0 : freq[strc][lo - 1]);
  long long ans = 0;
  if (freqLeft == max((hi - lo + 1) / 2, 1))
    ans += solve(mid + 1, hi, strc + 1);
  else if (freqRight == max((hi - lo + 1) / 2, 1)) {
    ans += solve(lo, mid, strc + 1);
  } else {
    long long tmp1 = 0, tmp2 = 0;
    if (freqLeft > freqRight) {
      ans +=
          max(((hi - lo + 1) / 2) - freqLeft, 1) + solve(mid + 1, hi, strc + 1);
    } else if (freqRight > freqLeft) {
      ans += max(((hi - lo + 1) / 2) - freqRight, 1) + solve(lo, mid, strc + 1);
    } else {
      tmp1 = max(((hi - lo + 1) / 2) - freqRight, 1) +
             solve(mid + 1, hi, strc + 1);
      ;
      tmp2 = max(((hi - lo + 1) / 2) - freqRight, 1) + solve(lo, mid, strc + 1);
      ans += min(tmp1, tmp2);
    }
  }
  return mem[lo][strc] = ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> tc;
  while (tc--) {
    cin >> n;
    cin >> s;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j <= 'z' - 'a'; j++) {
        freq[j][i] = 0;
        mem[i][j] = -1;
      }
    }
    for (int i = 0; i < n; i++) {
      freq[s[i] - 'a'][i]++;
    }
    for (int i = 0; i <= 'z' - 'a'; i++) {
      for (int j = 1; j < n; j++) freq[i][j] += freq[i][j - 1];
    }
    int hi = n - 1, lo = 0, mid;
    int strc = 0;
    long long ans = 0;
    cout << solve() << endl;
  }
  return 0;
}
