#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, M = 1e6 + 6, OO = 0x3f3f3f3f;
int tc;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> tc;
  while (tc--) {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int freq[26][n + 2];
    memset(freq, 0, sizeof freq);
    for (int i = 0; i < n; i++) {
      freq[s[i] - 'a'][i]++;
    }
    for (int i = 0; i <= 'z' - 'a'; i++) {
      for (int j = 1; j < n; j++) freq[i][j] += freq[i][j - 1];
    }
    int hi = n - 1, lo = 0, mid;
    int strc = 0;
    long long ans = 0;
    while (lo <= hi) {
      mid = (hi + lo) / 2;
      int freqRight = freq[strc][hi] - freq[strc][mid];
      int freqLeft = freq[strc][mid] - (lo == 0 ? 0 : freq[strc][lo - 1]);
      if (freqLeft == max((hi - lo + 1) / 2, 1)) {
        lo = mid + 1;
        strc++;
      } else if (freqRight == max((hi - lo + 1) / 2, 1)) {
        hi = mid;
        strc++;
      } else {
        if (freqLeft >= freqRight) {
          ans += max(((hi - lo + 1) / 2) - freqLeft, 1);
          lo = mid + 1;
          strc++;
        } else {
          ans += max(((hi - lo + 1) / 2) - freqRight, 1);
          hi = mid;
          strc++;
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}
