#include <bits/stdc++.h>
using namespace std;
int mx = 0, n;
vector<int> cnt(500000), last(500000);
void vec(int i, int lev, int total) {
  if (i >= n) {
    total += cnt[i];
    if (i % 2 == 0)
      total += last[i + 1];
    else
      total += last[i - 1];
    mx = max(mx, total);
    return;
  }
  total += cnt[i];
  if (i % 2 == 0) {
    vec((i + 1) * 2, lev + 1, total);
    vec((i + 1) * 2 + 1, lev + 1, total);
  } else {
    vec((i - 1) * 2, lev + 1, total);
    vec((i - 1) * 2 + 1, lev + 1, total);
  }
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    for (int i = 0; i < 3 * n; i++) {
      cnt[i] = 0;
      last[i] = 0;
    }
    mx = 0;
    cin >> n;
    string str;
    cin >> str;
    if (n == 1) {
      if (str == "a")
        cout << 0 << endl;
      else
        cout << 1 << endl;
      continue;
    }
    if (n == 2) {
      if (str == "ab" || str == "ba")
        cout << 0 << endl;
      else if (str.find('a') < str.size() || str.find('b') < str.size())
        cout << 1 << endl;
      else
        cout << 2 << endl;
      continue;
    }
    for (int i = 0; i < n; i++) {
      int num = str[i] - 'a' + 1;
      int total = n / (1 << num);
      if (total != 0) cnt[(1 << num) + i / total]++;
      if (log(n) / log(2) + 1 == num) {
        num--;
        total = n / (1 << num);
        last[(1 << num) + i / total]++;
      }
    }
    vec(2, 1, 0);
    vec(3, 1, 0);
    cout << n - mx << endl;
  }
  return 0;
}
