#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
const char nl = '\n';
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vl = vector<ll>;
using pii = pair<ll, ll>;
using pll = pair<ll, ll>;
using str = string;
str to_string(char c) { return str(1, c); }
str to_string(bool b) { return b ? "true" : "false"; }
str to_string(const char* second) { return (str)second; }
str to_string(str second) { return second; }
template <class A>
str to_string(complex<A> c) {
  stringstream ss;
  ss << c;
  return ss.str();
}
str to_string(vector<bool> v) {
  str res = "{";
  for (ll i = 0; i < (ll)v.size(); i++) res += char('0' + v[i]);
  res += "}";
  return res;
}
template <size_t SZ>
str to_string(bitset<SZ> b) {
  str res = "";
  for (ll i = 0; i < b.size(); i++) res += char('0' + b[i]);
  return res;
}
template <class A, class B>
str to_string(pair<A, B> p);
template <class T>
str to_string(T v) {
  bool fst = 1;
  str res = "{";
  for (const auto& x : v) {
    if (!fst) res += ", ";
    fst = 0;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <class A, class B>
str to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
void DBG() { cerr << "]" << endl; }
template <class H, class... T>
void DBG(H h, T... t) {
  cerr << to_string(h);
  if (sizeof...(t)) cerr << ", ";
  DBG(t...);
}
ll n;
string c;
vector<vi> pref;
set<ll> vis;
bool notone = 0;
ll bruh(ll idx, char tr, ll len) {
  vis.insert(idx);
  ll amt =
      pref[idx + len - 1][tr - 'a'] - ((idx > 0) ? pref[idx - 1][tr - 'a'] : 0);
  0;
  ll add = len - amt;
  if (len == n / 2) {
    return add;
  } else {
    if (len == 1 && notone) {
      if ((idx + 1) / 2 == idx / 2) {
        ;
        notone = 0;
        add += bruh(idx + 1, tr - 1, len);
      } else {
        notone = 0;
        add += bruh(idx - 1, tr - 1, len);
      }
    } else {
      bool minus = 1;
      if ((idx + len * 2) / (len * 2) * (len * 2) / (len * 4) ==
          idx / (len * 4)) {
        minus = 0;
      }
      if (!minus) {
        add += bruh((idx + len * 2) / (len * 2) * (len * 2), tr - 1, len * 2);
      } else {
        add += bruh((idx - len * 2) / (len * 2) * (len * 2), tr - 1, len * 2);
      }
    }
  }
  return add;
}
void solve() {
  cin >> n >> c;
  if (n == 1) {
    if (c[0] == 'a')
      cout << 0 << nl;
    else {
      cout << 1 << nl;
    }
    return;
  } else if (n == 2) {
    sort(c.begin(), c.end());
    ll ans = 0;
    if (c[0] == 'a' && c[1] == 'b') {
      cout << 0 << nl;
    } else {
      if (c[0] == 'a') {
        cout << 1 << nl;
      } else if (c[0] == 'b') {
        cout << 1 << nl;
      } else {
        cout << 2 << nl;
      }
    }
    return;
  }
  ll x = 1;
  ll atharv = 0;
  for (; x != n; atharv++) {
    x *= 2;
  }
  ll amt = atharv + 1;
  pref.resize(n);
  for (ll i = 0; i < n; i++) {
    pref[i].resize(26);
  }
  for (ll i = 0; i < n; i++) {
    for (ll j = 0; j < 26; j++) {
      if (i) pref[i][j] = pref[i - 1][j];
    }
    pref[i][c[i] - 'a']++;
  }
  0;
  ll ans = 1e9;
  for (ll i = 0; i < n; i++) {
    notone = 1;
    vis.clear();
    ans = min(bruh(i, 'a' + amt - 1, 1), ans);
    0;
    0;
  }
  cout << ans << nl;
  pref.clear();
}
signed main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  ll t;
  cin >> t;
  while (t--) solve();
}
