#include <bits/stdc++.h>
using namespace std;
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const long double pii = 3.14159265359;
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 200001;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int T;
  cin >> T;
  while (T-- != 0) {
    int N;
    cin >> N;
    int p2 = 0;
    while (1 << (p2) != N) p2++;
    string str;
    cin >> str;
    if (N == 1) {
      if (str[0] == 'a')
        cout << 0 << nl;
      else
        cout << 1 << nl;
      continue;
    }
    vector<int> v[p2];
    for (int x = 1; x < N; x += 2) {
      if (str[x] == 'a' + p2 - 1) {
        if (str[x - 1] == 'a' + p2)
          v[0].push_back(0);
        else
          v[0].push_back(1);
      } else if (str[x - 1] == 'a' + p2 - 1) {
        if (str[x] == 'a' + p2)
          v[0].push_back(0);
        else
          v[0].push_back(1);
      } else if (str[x] == 'a' + p2) {
        if (str[x - 1] == 'a' + p2 - 1)
          v[0].push_back(0);
        else
          v[0].push_back(1);
      } else if (str[x - 1] == 'a' + p2) {
        if (str[x] == 'a' + p2 - 1)
          v[0].push_back(0);
        else
          v[0].push_back(1);
      } else
        v[0].push_back(2);
    }
    int level = 0;
    while (level++ < p2 - 1) {
      int point = 0;
      int si = 0, ei = 1 << (level);
      while (si < 2 * (int)(v[level - 1]).size()) {
        int v1 = 0, v2 = 0;
        for (int x = ei; x < (ei + (1 << level)); x++) {
          if (str[x] != 'a' + p2 - level - 1) v2++;
        }
        v2 += v[level - 1][point++];
        for (int x = si; x < (ei); x++) {
          if (str[x] != 'a' + p2 - level - 1) v1++;
        }
        v1 += v[level - 1][point++];
        v[level].push_back(min(v1, v2));
        si += 1 << (level + 1);
        ei = si + (1 << level);
      }
    }
    cout << v[level - 1][0] << nl;
  }
  return 0;
}
