#include <bits/stdc++.h>
using namespace std;
const long long MAX_VALUE = LONG_MAX;
const long long MIN_VALUE = LONG_MIN;
const unsigned long long U_MAX_VALUE = ULLONG_MAX;
long long co;
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
long long max(long long a, long long b) {
  if (a > b)
    return a;
  else
    return b;
}
long long min(long long a, long long b) {
  if (a < b)
    return a;
  else
    return b;
}
void sieve();
void solve();
void setPrimeList();
bool isPrimeN(long long n);
bool isInside(long long cr, long long cc, long long r, long long c);
long long modulo_multiplication(long long a, long long b, long long mod);
long long mod_power(long long x, unsigned long long y, long long p);
long long count1[26][1000000];
void bfs(long long s, vector<long long> adj[], bool visited[]);
const long long MAX_N = 1e5;
const long long MOD = 1e9 + 7;
bool isPrime[MAX_N + 1];
vector<long long> primeList;
signed main() {
  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  long long t = 1;
  cin >> t;
  while (t--) {
    solve();
    cout << "\n";
  }
}
long long calc_occr(string s, long long start, long long end, char c) {
  return (end - start + 1) -
         (count1[c - 'a'][end + 1] - count1[c - 'a'][start]);
}
long long fun(string s, long long start, long long end, long long win_size,
              char c) {
  cout << start << " " << end << '\n';
  co++;
  if (win_size > 0) {
    if (win_size == 1) {
      char t = c;
      long long val1 = calc_occr(s, start, start + win_size - 1, c);
      c++;
      long long val2 = calc_occr(s, start + win_size, end, c);
      long long val3 = calc_occr(s, start, start + win_size - 1, c);
      long long val4 = calc_occr(s, start + win_size, end, t);
      return min(val1 + val2, val3 + val4);
    }
    long long val1 = calc_occr(s, start, start + win_size - 1, c);
    long long val2 = calc_occr(s, start + win_size, end, c);
    c++;
    long long return_val =
        min(val1 + fun(s, start + win_size, end, win_size / 2, c),
            val2 + fun(s, start, start + win_size - 1, win_size / 2, c));
    return return_val;
  }
  return 0;
}
void solve() {
  long long n;
  cin >> n;
  string s;
  cin >> s;
  for (long long i = 0; i < 26; i++) {
    for (long long j = 0; j < n; j++) {
      if (s[j] == 'a' + i) {
        count1[i][j + 1] = (count1[i][j] + 1);
      } else {
        count1[i][j + 1] = count1[i][j];
      }
    }
  }
  long long ans = 0;
  long long win_size = n / 2;
  if (n == 1) {
    if (s[0] != 'a') {
      cout << 1;
      return;
    }
    cout << 0;
    return;
  }
  cout << fun(s, 0, n - 1, n / 2, 'a');
}
void sieve() {
  memset(isPrime, true, sizeof(isPrime));
  for (long long i = 2; i <= MAX_N; i++) {
    if (isPrime[i]) {
      for (long long j = 2 * i; j <= MAX_N; j += i) {
        isPrime[j] = false;
      }
    }
  }
}
bool isPrimeN(long long n) {
  if (n == 1) return false;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
void setPrimeList() {
  for (long long i = 2; i < MAX_N; i++) {
    if (isPrime[i] == true) {
      primeList.push_back(i);
    }
  }
}
long long mod_power(long long a, long long b, long long M = MOD) {
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % M;
    a = (a * a) % M;
    b >>= 1;
  }
  return res;
}
long long modulo_multiplication(long long a, long long b, long long mod) {
  long long res = 0;
  a %= mod;
  while (b) {
    if (b & 1) res = (res + a) % mod;
    a = (2 * a) % mod;
    b >>= 1;
  }
  return res;
}
void bfs(long long s, vector<long long> adj[], bool visited[]) {
  queue<long long> queue;
  visited[s] = true;
  queue.push(s);
  vector<long long>::iterator i;
  while (!queue.empty()) {
    s = queue.front();
    queue.pop();
    for (i = adj[s].begin(); i != adj[s].end(); ++i) {
      if (!visited[*i]) {
        visited[*i] = true;
        queue.push(*i);
      }
    }
  }
}
bool isInside(long long cr, long long cc, long long r, long long c) {
  if (cr < 0) return 0;
  if (cc < 0) return 0;
  if (cr >= r) return 0;
  if (cc >= c) return 0;
  return 1;
}
