#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using dd = double;
using pll = pair<ll, ll>;
using tll = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vdd = vector<dd>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vvll = vector<vll>;
using vvdd = vector<vdd>;
using vvpll = vector<vpll>;
using vvtll = vector<vtll>;
using vvvll = vector<vvll>;
using vvvdd = vector<vvdd>;
using vvvpll = vector<vvpll>;
using vvvtll = vector<vvtll>;
using vvvvll = vector<vvvll>;
using vvvvdd = vector<vvvdd>;
using vvvvpll = vector<vvvpll>;
using vvvvtll = vector<vvvtll>;
constexpr ll INF = 1LL << 60;
constexpr dd EPS = 1e-11;
constexpr dd PI = 3.1415926535897932;
struct Fast {
  Fast() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(std::numeric_limits<double>::max_digits10);
  }
} fast;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline T MaxE(vector<T> &v, ll S, ll E) {
  T m = v[S];
  for (ll i = (S); i <= (E); i++) chmax(m, v[i]);
  return m;
}
template <class T>
inline T MinE(vector<T> &v, ll S, ll E) {
  T m = v[S];
  for (ll i = (S); i <= (E); i++) chmin(m, v[i]);
  return m;
}
template <class T>
inline T MaxE(vector<T> &v, ll N) {
  return MaxE(v, 0, N - 1);
}
template <class T>
inline T MinE(vector<T> &v, ll N) {
  return MinE(v, 0, N - 1);
}
template <class T>
inline T MaxE(vector<T> &v) {
  return MaxE(v, (ll)v.size());
}
template <class T>
inline T MinE(vector<T> &v) {
  return MinE(v, (ll)v.size());
}
template <class T>
inline ll MaxI(vector<T> &v, ll S, ll E) {
  ll m = S;
  for (ll i = (S); i <= (E); i++) {
    if (v[i] > v[m]) m = i;
  }
  return m;
}
template <class T>
inline ll MinI(vector<T> &v, ll S, ll E) {
  ll m = S;
  for (ll i = (S); i <= (E); i++) {
    if (v[i] < v[m]) m = i;
  }
  return m;
}
template <class T>
inline ll MaxI(vector<T> &v, ll N) {
  return MaxI(v, 0, N - 1);
}
template <class T>
inline ll MinI(vector<T> &v, ll N) {
  return MinI(v, 0, N - 1);
}
template <class T>
inline ll MaxI(vector<T> &v) {
  return MaxI(v, (ll)v.size());
}
template <class T>
inline ll MinI(vector<T> &v) {
  return MinI(v, (ll)v.size());
}
template <class T>
inline T Sum(vector<T> &v, ll S, ll E) {
  T s = v[S];
  for (ll i = (S + 1); i <= (E); i++) s += v[i];
  return s;
}
template <class T>
inline T Sum(vector<T> &v, ll N) {
  return Sum(v, 0, N - 1);
}
template <class T>
inline T Sum(vector<T> &v) {
  return Sum(v, v.size());
}
template <class T>
inline ll sz(T &v) {
  return (ll)v.size();
}
template <class T>
inline T POW(T a, ll n) {
  T r = 1;
  for (; n > 0; n >>= 1, a *= a) {
    if (n & 1) r *= a;
  }
  return r;
}
inline ll POW(int a, ll n) { return POW((ll)a, n); }
inline ll CEIL(ll a, ll b) { return (a + b - 1) / b; }
ll Gcd(ll a, ll b) { return (b == 0) ? a : Gcd(b, a % b); }
ll Lcm(ll a, ll b) { return a * b / Gcd(a, b); }
inline ll MSB(ll a) {
  for (ll o = 63, x = -1;;) {
    ll m = (o + x) / 2;
    if (a < (1LL << m))
      o = m;
    else
      x = m;
    if (o - x == 1) return x;
  }
}
inline ll Upper2N(ll s) { return 1LL << MSB(s) << 1; }
inline vll Bit2Idx(ll m) {
  vll v;
  for (ll i = 0; m; m >>= 1, i++)
    if (m & 1) v.push_back(i);
  return move(v);
}
inline ll BitNum(ll m) {
  for (ll c = 0;; m >>= 1) {
    c += m & 1;
    if (!m) return c;
  }
}
inline ll Bit(ll s, ll i) { return (s >> i) & 1; }
[[nodiscard]] inline ll BitOn(ll s, ll i) { return s | (1LL << i); }
[[nodiscard]] inline ll BitOff(ll s, ll i) { return s & ~(1LL << i); }
[[nodiscard]] inline ll BitCut(ll s, ll i) { return s & (1LL << ++i) - 1; }
inline vll str2num(string &s, ll N) {
  vll v(N);
  for (ll i = (0); i <= ((N)-1); i++) v[i] = (ll)(s[i] - '0');
  return move(v);
}
inline vll ALP2num(string &s, ll N) {
  vll v(N);
  for (ll i = (0); i <= ((N)-1); i++) v[i] = (ll)(s[i] - 'A');
  return move(v);
}
inline vll alp2num(string &s, ll N) {
  vll v(N);
  for (ll i = (0); i <= ((N)-1); i++) v[i] = (ll)(s[i] - 'a');
  return move(v);
}
template <class T>
inline ll FloorIdx(vector<T> &v, T x) {
  return upper_bound((v).begin(), (v).end(), x) - v.begin() - 1;
}
template <class T>
inline ll CeilIdx(vector<T> &v, T x) {
  return lower_bound((v).begin(), (v).end(), x) - v.begin();
}
template <class T>
inline ll UnderNumOf(vector<T> &v, T x) {
  return upper_bound(v.begin(), v.end(), x) - v.begin();
}
template <class T, class Pr>
inline ll UnderNumOf(vector<T> &v, T x, Pr pred) {
  return upper_bound(v.begin(), v.end(), x, pred) - v.begin();
}
template <class T>
inline ll OverNumOf(vector<T> &v, T x) {
  return (ll)v.size() - (lower_bound(v.begin(), v.end(), x) - v.begin());
}
template <class T, class Pr>
inline ll OverNumOf(vector<T> &v, T x, Pr pred) {
  return (ll)v.size() - (lower_bound(v.begin(), v.end(), x, pred) - v.begin());
}
template <class T = ll>
inline vector<T> cinv(ll N) {
  vector<T> v(N);
  for (ll i = (0); i <= ((N)-1); i++) cin >> v[i];
  return move(v);
}
template <class T = ll, class S = ll>
inline vector<pair<T, S>> cinv2(ll N) {
  vector<pair<T, S>> v(N);
  for (ll i = (0); i <= ((N)-1); i++) {
    cin >> v[i].first >> v[i].second;
  }
  return move(v);
}
template <class T = ll, class S = ll, class R = ll>
inline vector<tuple<T, S, R>> cinv3(ll N) {
  vector<tuple<T, S, R>> v(N);
  for (ll i = (0); i <= ((N)-1); i++) {
    cin >> get<0>(v[i]) >> get<1>(v[i]) >> get<2>(v[i]);
  }
  return move(v);
}
template <class T = ll, class S = ll, class R = ll, class Q = ll>
inline vector<tuple<T, S, R, Q>> cinv4(ll N) {
  vector<tuple<T, S, R, Q>> v(N);
  for (ll i = (0); i <= ((N)-1); i++) {
    cin >> get<0>(v[i]) >> get<1>(v[i]) >> get<2>(v[i]) >> get<3>(v[i]);
  }
  return move(v);
}
template <class T = ll>
inline vector<vector<T>> cinvv(ll N, ll M) {
  vector<vector<T>> vv(N);
  for (ll i = (0); i <= ((N)-1); i++) vv[i] = cinv(M);
  return move(vv);
}
template <class T>
inline void coutv(vector<T> &v, string d = " ") {
  ll N = (ll)v.size();
  for (ll i = (0); i <= ((N)-1); i++) {
    cout << v[i] << ((i == N - 1) ? "" : d);
  }
  cout << '\n';
}
template <class T>
inline void coutv(deque<T> &v, string d = " ") {
  ll N = (ll)v.size();
  for (ll i = (0); i <= ((N)-1); i++) {
    cout << v[i] << ((i == N - 1) ? "" : d);
  }
  cout << '\n';
}
template <class T>
void bye(T a) {
  cout << a << '\n';
  exit(0);
}
template <class T>
void Dump(vector<T> &v) {}
template <class T>
void Dump(vector<vector<T>> &v) {}
template <class T>
void Dump(vector<vector<vector<T>>> &v) {}
template <class T>
void Dump(vector<vector<vector<vector<T>>>> &v) {}
template <class T>
void Dump(vector<vector<vector<vector<vector<T>>>>> &v) {}
template <ll MOD>
struct mll_ {
  ll val;
  mll_(ll v = 0) : val(v % MOD) {
    if (val < 0) val += MOD;
  }
  mll_ operator-() const { return -val; }
  mll_ operator+(const mll_ &b) const { return val + b.val; }
  mll_ operator-(const mll_ &b) const { return val - b.val; }
  mll_ operator*(const mll_ &b) const { return val * b.val; }
  mll_ operator/(const mll_ &b) const { return mll_(*this) /= b; }
  mll_ operator+(ll b) const { return *this + mll_(b); }
  mll_ operator-(ll b) const { return *this - mll_(b); }
  mll_ operator*(ll b) const { return *this * mll_(b); }
  friend mll_ operator+(ll a, const mll_ &b) { return b + a; }
  friend mll_ operator-(ll a, const mll_ &b) { return -b + a; }
  friend mll_ operator*(ll a, const mll_ &b) { return b * a; }
  friend mll_ operator/(ll a, const mll_ &b) { return mll_(a) / b; }
  mll_ &operator+=(const mll_ &b) {
    val = (val + b.val) % MOD;
    return *this;
  }
  mll_ &operator-=(const mll_ &b) {
    val = (val + MOD - b.val) % MOD;
    return *this;
  }
  mll_ &operator*=(const mll_ &b) {
    val = (val * b.val) % MOD;
    return *this;
  }
  mll_ &operator/=(const mll_ &b) {
    ll c = b.val, d = MOD, u = 1, v = 0;
    while (d) {
      ll t = c / d;
      c -= t * d;
      swap(c, d);
      u -= t * v;
      swap(u, v);
    }
    val = val * u % MOD;
    if (val < 0) val += MOD;
    return *this;
  }
  mll_ &operator+=(ll b) { return *this += mll_(b); }
  mll_ &operator-=(ll b) { return *this -= mll_(b); }
  mll_ &operator*=(ll b) { return *this *= mll_(b); }
  mll_ &operator/=(ll b) { return *this /= mll_(b); }
  bool operator==(const mll_ &b) { return val == b.val; }
  bool operator!=(const mll_ &b) { return val != b.val; }
  bool operator==(ll b) { return *this == mll_(b); }
  bool operator!=(ll b) { return *this != mll_(b); }
  friend bool operator==(ll a, const mll_ &b) { return mll_(a) == b.val; }
  friend bool operator!=(ll a, const mll_ &b) { return mll_(a) != b.val; }
  friend ostream &operator<<(ostream &os, const mll_ &a) { return os << a.val; }
  friend istream &operator>>(istream &is, mll_ &a) { return is >> a.val; }
  static mll_ Combination(ll a, ll b) {
    chmin(b, a - b);
    if (b < 0) return mll_(0);
    mll_ c = 1;
    for (ll i = (0); i <= ((b)-1); i++) c *= a - i;
    for (ll i = (0); i <= ((b)-1); i++) c /= i + 1;
    return c;
  }
};
using mll = mll_<1000000007LL>;
using vmll = std::vector<mll>;
using vvmll = std::vector<vmll>;
using vvvmll = std::vector<vvmll>;
using vvvvmll = std::vector<vvvmll>;
using vvvvvmll = std::vector<vvvvmll>;
template <class T>
struct CumulativeSumG {
  ll s = 0, e = -1;
  vector<T> cum;
  CumulativeSumG(){};
  CumulativeSumG(vector<T> &v) : e(v.size() - 1), cum(e + 2) { ini(v); }
  CumulativeSumG(vector<T> &v, ll S, ll E) : s(S), e(E), cum(e - s + 2) {
    ini(v);
  }
  void Init(vector<T> &v) {
    e = v.size() - 1;
    cum.resize(e + 2);
    ini(v);
  }
  void Init(vector<T> &v, ll S, ll E) {
    s = S;
    e = E;
    cum.resize(e - s + 2);
    ini(v);
  }
  void Add(T x) {
    e++;
    cum.push_back(cum.back() + x);
  }
  T operator()(ll begin, ll end) { return cum[end + 1 - s] - cum[begin - s]; }
  void ini(vector<T> &v) {
    for (ll i = (s); i <= (e); i++) cum[i + 1 - s] = cum[i - s] + v[i];
  }
};
using CumulativeSum = CumulativeSumG<ll>;
vector<CumulativeSum> cum;
ll dfs(ll l, ll r, ll c) {
  if (l == r) {
    return cum[c](l, r);
  }
  ll m = (l + r) / 2;
  ll v1 = cum[c](l, m);
  ll u1 = dfs(m + 1, r, c + 1);
  ll v2 = cum[c](m + 1, r);
  ll u2 = dfs(l, m, c + 1);
  ll ret = max(v1 + u1, v2 + u2);
  return ret;
}
void solve() {
  ll n;
  cin >> n;
  string s;
  cin >> s;
  ll k = MSB(n);
  vvll cnt(k + 1, vll(n));
  for (ll i = (0); i <= (n - 1); i++) {
    ll val = (ll)(s[i] - 'a');
    if (val <= k) {
      cnt[val][i] = 1;
    }
  }
  cum.resize(k + 1);
  for (ll kk = (0); kk <= (k); kk++) {
    cum[kk].Init(cnt[kk]);
  }
  ll ans = n - dfs(0, n - 1, 0);
  cout << ans << '\n';
}
int main() {
  ll t;
  cin >> t;
  for (ll i = (0); i <= (t - 1); i++) {
    solve();
  }
  return 0;
}

### Prompt

Generate a cpp solution to the following problem:

You are given a string s[1 ... n] consisting of lowercase Latin letters. It is guaranteed that n = 2^k for some integer k ≥ 0.

The string s[1 ... n] is called c-good if at least one of the following three conditions is satisfied:

  * The length of s is 1, and it consists of the character c (i.e. s_1=c);
  * The length of s is greater than 1, the first half of the string consists of only the character c (i.e. s_1=s_2=...=s_{n/2}=c) and the second half of the string (i.e. the string s_{n/2 + 1}s_{n/2 + 2} ... s_n) is a (c+1)-good string; 
  * The length of s is greater than 1, the second half of the string consists of only the character c (i.e. s_{n/2 + 1}=s_{n/2 + 2}=...=s_n=c) and the first half of the string (i.e. the string s_1s_2 ... s_{n/2}) is a (c+1)-good string. 



For example: "aabc" is 'a'-good, "ffgheeee" is 'e'-good.

In one move, you can choose one index i from 1 to n and replace s_i with any lowercase Latin letter (any character from 'a' to 'z').

Your task is to find the minimum number of moves required to obtain an 'a'-good string from s (i.e. c-good string for c= 'a'). It is guaranteed that the answer always exists.

You have to answer t independent test cases.

Another example of an 'a'-good string is as follows. Consider the string s = "cdbbaaaa". It is an 'a'-good string, because:

  * the second half of the string ("aaaa") consists of only the character 'a'; 
  * the first half of the string ("cdbb") is 'b'-good string, because: 
    * the second half of the string ("bb") consists of only the character 'b'; 
    * the first half of the string ("cd") is 'c'-good string, because: 
      * the first half of the string ("c") consists of only the character 'c'; 
      * the second half of the string ("d") is 'd'-good string. 

Input

The first line of the input contains one integer t (1 ≤ t ≤ 2 ⋅ 10^4) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1 ≤ n ≤ 131~072) — the length of s. It is guaranteed that n = 2^k for some integer k ≥ 0. The second line of the test case contains the string s consisting of n lowercase Latin letters.

It is guaranteed that the sum of n does not exceed 2 ⋅ 10^5 (∑ n ≤ 2 ⋅ 10^5).

Output

For each test case, print the answer — the minimum number of moves required to obtain an 'a'-good string from s (i.e. c-good string with c = 'a'). It is guaranteed that the answer exists.

Example

Input


6
8
bbdcaaaa
8
asdfghjk
8
ceaaaabb
8
bbaaddcc
1
z
2
ac


Output


0
7
4
5
1
1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using dd = double;
using pll = pair<ll, ll>;
using tll = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vdd = vector<dd>;
using vpll = vector<pll>;
using vtll = vector<tll>;
using vvll = vector<vll>;
using vvdd = vector<vdd>;
using vvpll = vector<vpll>;
using vvtll = vector<vtll>;
using vvvll = vector<vvll>;
using vvvdd = vector<vvdd>;
using vvvpll = vector<vvpll>;
using vvvtll = vector<vvtll>;
using vvvvll = vector<vvvll>;
using vvvvdd = vector<vvvdd>;
using vvvvpll = vector<vvvpll>;
using vvvvtll = vector<vvvtll>;
constexpr ll INF = 1LL << 60;
constexpr dd EPS = 1e-11;
constexpr dd PI = 3.1415926535897932;
struct Fast {
  Fast() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(std::numeric_limits<double>::max_digits10);
  }
} fast;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline T MaxE(vector<T> &v, ll S, ll E) {
  T m = v[S];
  for (ll i = (S); i <= (E); i++) chmax(m, v[i]);
  return m;
}
template <class T>
inline T MinE(vector<T> &v, ll S, ll E) {
  T m = v[S];
  for (ll i = (S); i <= (E); i++) chmin(m, v[i]);
  return m;
}
template <class T>
inline T MaxE(vector<T> &v, ll N) {
  return MaxE(v, 0, N - 1);
}
template <class T>
inline T MinE(vector<T> &v, ll N) {
  return MinE(v, 0, N - 1);
}
template <class T>
inline T MaxE(vector<T> &v) {
  return MaxE(v, (ll)v.size());
}
template <class T>
inline T MinE(vector<T> &v) {
  return MinE(v, (ll)v.size());
}
template <class T>
inline ll MaxI(vector<T> &v, ll S, ll E) {
  ll m = S;
  for (ll i = (S); i <= (E); i++) {
    if (v[i] > v[m]) m = i;
  }
  return m;
}
template <class T>
inline ll MinI(vector<T> &v, ll S, ll E) {
  ll m = S;
  for (ll i = (S); i <= (E); i++) {
    if (v[i] < v[m]) m = i;
  }
  return m;
}
template <class T>
inline ll MaxI(vector<T> &v, ll N) {
  return MaxI(v, 0, N - 1);
}
template <class T>
inline ll MinI(vector<T> &v, ll N) {
  return MinI(v, 0, N - 1);
}
template <class T>
inline ll MaxI(vector<T> &v) {
  return MaxI(v, (ll)v.size());
}
template <class T>
inline ll MinI(vector<T> &v) {
  return MinI(v, (ll)v.size());
}
template <class T>
inline T Sum(vector<T> &v, ll S, ll E) {
  T s = v[S];
  for (ll i = (S + 1); i <= (E); i++) s += v[i];
  return s;
}
template <class T>
inline T Sum(vector<T> &v, ll N) {
  return Sum(v, 0, N - 1);
}
template <class T>
inline T Sum(vector<T> &v) {
  return Sum(v, v.size());
}
template <class T>
inline ll sz(T &v) {
  return (ll)v.size();
}
template <class T>
inline T POW(T a, ll n) {
  T r = 1;
  for (; n > 0; n >>= 1, a *= a) {
    if (n & 1) r *= a;
  }
  return r;
}
inline ll POW(int a, ll n) { return POW((ll)a, n); }
inline ll CEIL(ll a, ll b) { return (a + b - 1) / b; }
ll Gcd(ll a, ll b) { return (b == 0) ? a : Gcd(b, a % b); }
ll Lcm(ll a, ll b) { return a * b / Gcd(a, b); }
inline ll MSB(ll a) {
  for (ll o = 63, x = -1;;) {
    ll m = (o + x) / 2;
    if (a < (1LL << m))
      o = m;
    else
      x = m;
    if (o - x == 1) return x;
  }
}
inline ll Upper2N(ll s) { return 1LL << MSB(s) << 1; }
inline vll Bit2Idx(ll m) {
  vll v;
  for (ll i = 0; m; m >>= 1, i++)
    if (m & 1) v.push_back(i);
  return move(v);
}
inline ll BitNum(ll m) {
  for (ll c = 0;; m >>= 1) {
    c += m & 1;
    if (!m) return c;
  }
}
inline ll Bit(ll s, ll i) { return (s >> i) & 1; }
[[nodiscard]] inline ll BitOn(ll s, ll i) { return s | (1LL << i); }
[[nodiscard]] inline ll BitOff(ll s, ll i) { return s & ~(1LL << i); }
[[nodiscard]] inline ll BitCut(ll s, ll i) { return s & (1LL << ++i) - 1; }
inline vll str2num(string &s, ll N) {
  vll v(N);
  for (ll i = (0); i <= ((N)-1); i++) v[i] = (ll)(s[i] - '0');
  return move(v);
}
inline vll ALP2num(string &s, ll N) {
  vll v(N);
  for (ll i = (0); i <= ((N)-1); i++) v[i] = (ll)(s[i] - 'A');
  return move(v);
}
inline vll alp2num(string &s, ll N) {
  vll v(N);
  for (ll i = (0); i <= ((N)-1); i++) v[i] = (ll)(s[i] - 'a');
  return move(v);
}
template <class T>
inline ll FloorIdx(vector<T> &v, T x) {
  return upper_bound((v).begin(), (v).end(), x) - v.begin() - 1;
}
template <class T>
inline ll CeilIdx(vector<T> &v, T x) {
  return lower_bound((v).begin(), (v).end(), x) - v.begin();
}
template <class T>
inline ll UnderNumOf(vector<T> &v, T x) {
  return upper_bound(v.begin(), v.end(), x) - v.begin();
}
template <class T, class Pr>
inline ll UnderNumOf(vector<T> &v, T x, Pr pred) {
  return upper_bound(v.begin(), v.end(), x, pred) - v.begin();
}
template <class T>
inline ll OverNumOf(vector<T> &v, T x) {
  return (ll)v.size() - (lower_bound(v.begin(), v.end(), x) - v.begin());
}
template <class T, class Pr>
inline ll OverNumOf(vector<T> &v, T x, Pr pred) {
  return (ll)v.size() - (lower_bound(v.begin(), v.end(), x, pred) - v.begin());
}
template <class T = ll>
inline vector<T> cinv(ll N) {
  vector<T> v(N);
  for (ll i = (0); i <= ((N)-1); i++) cin >> v[i];
  return move(v);
}
template <class T = ll, class S = ll>
inline vector<pair<T, S>> cinv2(ll N) {
  vector<pair<T, S>> v(N);
  for (ll i = (0); i <= ((N)-1); i++) {
    cin >> v[i].first >> v[i].second;
  }
  return move(v);
}
template <class T = ll, class S = ll, class R = ll>
inline vector<tuple<T, S, R>> cinv3(ll N) {
  vector<tuple<T, S, R>> v(N);
  for (ll i = (0); i <= ((N)-1); i++) {
    cin >> get<0>(v[i]) >> get<1>(v[i]) >> get<2>(v[i]);
  }
  return move(v);
}
template <class T = ll, class S = ll, class R = ll, class Q = ll>
inline vector<tuple<T, S, R, Q>> cinv4(ll N) {
  vector<tuple<T, S, R, Q>> v(N);
  for (ll i = (0); i <= ((N)-1); i++) {
    cin >> get<0>(v[i]) >> get<1>(v[i]) >> get<2>(v[i]) >> get<3>(v[i]);
  }
  return move(v);
}
template <class T = ll>
inline vector<vector<T>> cinvv(ll N, ll M) {
  vector<vector<T>> vv(N);
  for (ll i = (0); i <= ((N)-1); i++) vv[i] = cinv(M);
  return move(vv);
}
template <class T>
inline void coutv(vector<T> &v, string d = " ") {
  ll N = (ll)v.size();
  for (ll i = (0); i <= ((N)-1); i++) {
    cout << v[i] << ((i == N - 1) ? "" : d);
  }
  cout << '\n';
}
template <class T>
inline void coutv(deque<T> &v, string d = " ") {
  ll N = (ll)v.size();
  for (ll i = (0); i <= ((N)-1); i++) {
    cout << v[i] << ((i == N - 1) ? "" : d);
  }
  cout << '\n';
}
template <class T>
void bye(T a) {
  cout << a << '\n';
  exit(0);
}
template <class T>
void Dump(vector<T> &v) {}
template <class T>
void Dump(vector<vector<T>> &v) {}
template <class T>
void Dump(vector<vector<vector<T>>> &v) {}
template <class T>
void Dump(vector<vector<vector<vector<T>>>> &v) {}
template <class T>
void Dump(vector<vector<vector<vector<vector<T>>>>> &v) {}
template <ll MOD>
struct mll_ {
  ll val;
  mll_(ll v = 0) : val(v % MOD) {
    if (val < 0) val += MOD;
  }
  mll_ operator-() const { return -val; }
  mll_ operator+(const mll_ &b) const { return val + b.val; }
  mll_ operator-(const mll_ &b) const { return val - b.val; }
  mll_ operator*(const mll_ &b) const { return val * b.val; }
  mll_ operator/(const mll_ &b) const { return mll_(*this) /= b; }
  mll_ operator+(ll b) const { return *this + mll_(b); }
  mll_ operator-(ll b) const { return *this - mll_(b); }
  mll_ operator*(ll b) const { return *this * mll_(b); }
  friend mll_ operator+(ll a, const mll_ &b) { return b + a; }
  friend mll_ operator-(ll a, const mll_ &b) { return -b + a; }
  friend mll_ operator*(ll a, const mll_ &b) { return b * a; }
  friend mll_ operator/(ll a, const mll_ &b) { return mll_(a) / b; }
  mll_ &operator+=(const mll_ &b) {
    val = (val + b.val) % MOD;
    return *this;
  }
  mll_ &operator-=(const mll_ &b) {
    val = (val + MOD - b.val) % MOD;
    return *this;
  }
  mll_ &operator*=(const mll_ &b) {
    val = (val * b.val) % MOD;
    return *this;
  }
  mll_ &operator/=(const mll_ &b) {
    ll c = b.val, d = MOD, u = 1, v = 0;
    while (d) {
      ll t = c / d;
      c -= t * d;
      swap(c, d);
      u -= t * v;
      swap(u, v);
    }
    val = val * u % MOD;
    if (val < 0) val += MOD;
    return *this;
  }
  mll_ &operator+=(ll b) { return *this += mll_(b); }
  mll_ &operator-=(ll b) { return *this -= mll_(b); }
  mll_ &operator*=(ll b) { return *this *= mll_(b); }
  mll_ &operator/=(ll b) { return *this /= mll_(b); }
  bool operator==(const mll_ &b) { return val == b.val; }
  bool operator!=(const mll_ &b) { return val != b.val; }
  bool operator==(ll b) { return *this == mll_(b); }
  bool operator!=(ll b) { return *this != mll_(b); }
  friend bool operator==(ll a, const mll_ &b) { return mll_(a) == b.val; }
  friend bool operator!=(ll a, const mll_ &b) { return mll_(a) != b.val; }
  friend ostream &operator<<(ostream &os, const mll_ &a) { return os << a.val; }
  friend istream &operator>>(istream &is, mll_ &a) { return is >> a.val; }
  static mll_ Combination(ll a, ll b) {
    chmin(b, a - b);
    if (b < 0) return mll_(0);
    mll_ c = 1;
    for (ll i = (0); i <= ((b)-1); i++) c *= a - i;
    for (ll i = (0); i <= ((b)-1); i++) c /= i + 1;
    return c;
  }
};
using mll = mll_<1000000007LL>;
using vmll = std::vector<mll>;
using vvmll = std::vector<vmll>;
using vvvmll = std::vector<vvmll>;
using vvvvmll = std::vector<vvvmll>;
using vvvvvmll = std::vector<vvvvmll>;
template <class T>
struct CumulativeSumG {
  ll s = 0, e = -1;
  vector<T> cum;
  CumulativeSumG(){};
  CumulativeSumG(vector<T> &v) : e(v.size() - 1), cum(e + 2) { ini(v); }
  CumulativeSumG(vector<T> &v, ll S, ll E) : s(S), e(E), cum(e - s + 2) {
    ini(v);
  }
  void Init(vector<T> &v) {
    e = v.size() - 1;
    cum.resize(e + 2);
    ini(v);
  }
  void Init(vector<T> &v, ll S, ll E) {
    s = S;
    e = E;
    cum.resize(e - s + 2);
    ini(v);
  }
  void Add(T x) {
    e++;
    cum.push_back(cum.back() + x);
  }
  T operator()(ll begin, ll end) { return cum[end + 1 - s] - cum[begin - s]; }
  void ini(vector<T> &v) {
    for (ll i = (s); i <= (e); i++) cum[i + 1 - s] = cum[i - s] + v[i];
  }
};
using CumulativeSum = CumulativeSumG<ll>;
vector<CumulativeSum> cum;
ll dfs(ll l, ll r, ll c) {
  if (l == r) {
    return cum[c](l, r);
  }
  ll m = (l + r) / 2;
  ll v1 = cum[c](l, m);
  ll u1 = dfs(m + 1, r, c + 1);
  ll v2 = cum[c](m + 1, r);
  ll u2 = dfs(l, m, c + 1);
  ll ret = max(v1 + u1, v2 + u2);
  return ret;
}
void solve() {
  ll n;
  cin >> n;
  string s;
  cin >> s;
  ll k = MSB(n);
  vvll cnt(k + 1, vll(n));
  for (ll i = (0); i <= (n - 1); i++) {
    ll val = (ll)(s[i] - 'a');
    if (val <= k) {
      cnt[val][i] = 1;
    }
  }
  cum.resize(k + 1);
  for (ll kk = (0); kk <= (k); kk++) {
    cum[kk].Init(cnt[kk]);
  }
  ll ans = n - dfs(0, n - 1, 0);
  cout << ans << '\n';
}
int main() {
  ll t;
  cin >> t;
  for (ll i = (0); i <= (t - 1); i++) {
    solve();
  }
  return 0;
}

```