#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
ll call(ll i, ll j, string &s, ll c, map<pair<pair<ll, ll>, ll>, ll> &m) {
  if (i > j) return 0;
  if (i == j) {
    if (s[i] == c + 'a') return 0;
    return 1;
  }
  ll mid = (i + j) >> 1;
  ll a1 = 0, a2 = m[{{mid + 1, j}, c}];
  a1 = m[{{i, mid}, c}];
  return min(a2 + call(i, mid, s, c + 1, m),
             a1 + call(mid + 1, j, s, c + 1, m));
}
int main() {
  ll t = 1;
  cin >> t;
  while (t--) {
    ll n;
    cin >> n;
    string s;
    map<pair<pair<ll, ll>, ll>, ll> m;
    cin >> s;
    ll cnt = 0;
    while ((1 << cnt) != n) cnt++;
    cnt++;
    ll fre[26] = {0};
    ll pre[26];
    memset(pre, -1, sizeof(pre));
    for (ll i = 0; i < n; i++) {
      fre[s[i] - 'a']++;
      for (ll chr = 0; chr < cnt - 1; chr++) {
        if (i - pre[chr] == (n / 2) / (1 << chr)) {
          m[make_pair(make_pair(pre[chr] + 1, i), chr)] =
              i - pre[chr] - fre[chr];
          fre[chr] = 0;
          pre[chr] = i;
        }
      }
      if (s[i] == (cnt - 1) + 'a') {
        m[{{i, i}, cnt - 1}] = 0;
      } else
        m[{{i, i}, cnt - 1}] = 1;
    }
    cout << call(0, n - 1, s, 0, m) << endl;
  }
}
