#include <bits/stdc++.h>
using namespace std;
template <typename T>
void deb(T v[], long long n) {
  if (false) cerr << "ARRAY   : ";
  long long i;
  for (i = 0; i < n; i++)
    if (false) cerr << v[i] << " ";
  if (false) cerr << endl;
}
template <typename T>
void deb(set<T> s) {
  if (false) cerr << "SET     : ";
  for (auto it : s)
    if (false) cerr << it << " ";
  if (false) cerr << endl;
}
template <typename T>
void deb(vector<T> v) {
  if (false) cerr << "VECTOR : ";
  long long i;
  for (i = 0; i < v.size(); i++)
    if (false) cerr << v[i] << " ";
  if (false) cerr << endl;
}
template <typename T>
void deb(stack<T> s) {
  if (false) cerr << "STACK   : ";
  stack<T> st = s;
  while (st.size()) {
    if (false) cerr << st.top() << " ";
    st.pop();
  };
  if (false) cerr << endl;
}
template <typename T>
void deb(queue<T> q) {
  if (false) cerr << "Queue   : ";
  queue<T> qq = q;
  while (qq.size()) {
    if (false) cerr << qq.front() << " ";
    qq.pop();
  };
  if (false) cerr << endl;
}
void deb(map<long long, long long> m) {
  if (false) cerr << "MAP : ";
  for (auto it : m)
    if (false) cerr << it.first << " : " << it.second << endl;
}
void deb(unordered_map<long long, long long> m) {
  if (false) cerr << "MAP : ";
  for (auto it : m)
    if (false) cerr << it.first << " : " << it.second << endl;
}
template <typename T>
T abs(T a) {
  return a < 0 ? a * -1 : a;
}
void swap(long long &x, long long &y);
bool isPrime(long long n);
long long power(long long x, long long y, long long p);
long long gcdExtended(long long a, long long b, long long *x, long long *y);
long long modInverse(long long b, long long m);
long long modDivide(long long a, long long b, long long m);
void simpleSieve(long long N, bool[]);
void PrimeDivisorSieve(long long N, long long prime[]);
class nCrModPClass {
 public:
  vector<long long> f, fi;
  long long N;
  long long MOD;
  long long poww(long long a, long long b, long long m) {
    long long ans = 1;
    while (b) {
      if (b & 1) ans = (ans * a) % m;
      b /= 2;
      a = (a * a) % m;
    }
    return ans;
  }
  long long modinvv(long long k) { return poww(k, MOD - 2, MOD); }
  nCrModPClass(long long size, long long mod) {
    MOD = mod;
    N = size + 10;
    f.resize(N);
    fi.resize(N);
    f[0] = f[1] = 1;
    for (long long i = 2; i < N; i++) f[i] = (f[i - 1] * i) % MOD;
    fi[N - 1] = modinvv(f[N - 1]);
    for (long long i = N - 2; i >= 0; i--) fi[i] = (fi[i + 1] * (i + 1)) % MOD;
  }
  long long nCrModPfromClass(long long n, long long r) {
    if (r > n) return 0;
    long long ret = f[n];
    ret %= MOD;
    ret *= fi[r];
    ret %= MOD;
    ret *= fi[n - r];
    ret %= MOD;
    return ret;
  }
};
long long testCases;
long long minTocs(string a, char c) {
  if (a.length() == 1) {
    return a[0] != c;
  }
  string lef, rig;
  long long dlef, drig;
  dlef = drig = 0;
  for (long long i = 0; i < a.length() / 2; i++) {
    dlef += a[i] != c;
    lef += a[i];
  }
  for (long long i = a.length() / 2; i < a.length(); i++) {
    drig += a[i] != c;
    rig += a[i];
  }
  return min(dlef + minTocs(rig, (char)c + 1),
             minTocs(lef, (char)c + 1) + drig);
}
int main() {
  testCases = 1;
  cin >> testCases;
  while (testCases--) {
    long long n;
    cin >> n;
    string s;
    cin >> s;
    cout << minTocs(s, 'a') << endl;
  }
  return 0;
}
void simpleSieve(long long N, bool prime[]) {
  long long i, j;
  for (i = 0; i < N + 1; i++) prime[i] = true;
  for (i = 2; i * i <= N; i++) {
    if (prime[i]) {
      for (j = i * i; j <= N; j += i) {
        prime[j] = false;
      }
    }
  }
}
void PrimeDivisorSieve(long long N, long long prime[]) {
  long long i, j;
  for (i = 0; i < N + 1; i++) prime[i] = i;
  for (i = 2; i * i <= N; i++) {
    if (prime[i] == i) {
      for (j = i; j <= N; j += i) {
        if (prime[j] == j) prime[j] = i;
      }
    }
  }
}
void swap(long long &x, long long &y) {
  x ^= y;
  y ^= x;
  x ^= y;
}
bool isPrime(long long n) {
  if (n <= 1) return false;
  for (long long i = 2; i < n; i++)
    if (n % i == 0) return false;
  return true;
}
long long power(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long gcdExtended(long long a, long long b, long long *x, long long *y) {
  if (a == 0) {
    *x = 0, *y = 1;
    return b;
  }
  long long x1, y1;
  long long gcd = gcdExtended(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
long long modInverse(long long b, long long m) {
  long long x, y;
  long long g = gcdExtended(b, m, &x, &y);
  if (g != 1) return -1;
  return (x % m + m) % m;
}
long long modDivide(long long a, long long b, long long m) {
  a = a % m;
  long long inv = modInverse(b, m);
  if (inv == -1)
    return -1;
  else
    return (inv * a) % m;
}

### Prompt

Please create a solution in CPP 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;
template <typename T>
void deb(T v[], long long n) {
  if (false) cerr << "ARRAY   : ";
  long long i;
  for (i = 0; i < n; i++)
    if (false) cerr << v[i] << " ";
  if (false) cerr << endl;
}
template <typename T>
void deb(set<T> s) {
  if (false) cerr << "SET     : ";
  for (auto it : s)
    if (false) cerr << it << " ";
  if (false) cerr << endl;
}
template <typename T>
void deb(vector<T> v) {
  if (false) cerr << "VECTOR : ";
  long long i;
  for (i = 0; i < v.size(); i++)
    if (false) cerr << v[i] << " ";
  if (false) cerr << endl;
}
template <typename T>
void deb(stack<T> s) {
  if (false) cerr << "STACK   : ";
  stack<T> st = s;
  while (st.size()) {
    if (false) cerr << st.top() << " ";
    st.pop();
  };
  if (false) cerr << endl;
}
template <typename T>
void deb(queue<T> q) {
  if (false) cerr << "Queue   : ";
  queue<T> qq = q;
  while (qq.size()) {
    if (false) cerr << qq.front() << " ";
    qq.pop();
  };
  if (false) cerr << endl;
}
void deb(map<long long, long long> m) {
  if (false) cerr << "MAP : ";
  for (auto it : m)
    if (false) cerr << it.first << " : " << it.second << endl;
}
void deb(unordered_map<long long, long long> m) {
  if (false) cerr << "MAP : ";
  for (auto it : m)
    if (false) cerr << it.first << " : " << it.second << endl;
}
template <typename T>
T abs(T a) {
  return a < 0 ? a * -1 : a;
}
void swap(long long &x, long long &y);
bool isPrime(long long n);
long long power(long long x, long long y, long long p);
long long gcdExtended(long long a, long long b, long long *x, long long *y);
long long modInverse(long long b, long long m);
long long modDivide(long long a, long long b, long long m);
void simpleSieve(long long N, bool[]);
void PrimeDivisorSieve(long long N, long long prime[]);
class nCrModPClass {
 public:
  vector<long long> f, fi;
  long long N;
  long long MOD;
  long long poww(long long a, long long b, long long m) {
    long long ans = 1;
    while (b) {
      if (b & 1) ans = (ans * a) % m;
      b /= 2;
      a = (a * a) % m;
    }
    return ans;
  }
  long long modinvv(long long k) { return poww(k, MOD - 2, MOD); }
  nCrModPClass(long long size, long long mod) {
    MOD = mod;
    N = size + 10;
    f.resize(N);
    fi.resize(N);
    f[0] = f[1] = 1;
    for (long long i = 2; i < N; i++) f[i] = (f[i - 1] * i) % MOD;
    fi[N - 1] = modinvv(f[N - 1]);
    for (long long i = N - 2; i >= 0; i--) fi[i] = (fi[i + 1] * (i + 1)) % MOD;
  }
  long long nCrModPfromClass(long long n, long long r) {
    if (r > n) return 0;
    long long ret = f[n];
    ret %= MOD;
    ret *= fi[r];
    ret %= MOD;
    ret *= fi[n - r];
    ret %= MOD;
    return ret;
  }
};
long long testCases;
long long minTocs(string a, char c) {
  if (a.length() == 1) {
    return a[0] != c;
  }
  string lef, rig;
  long long dlef, drig;
  dlef = drig = 0;
  for (long long i = 0; i < a.length() / 2; i++) {
    dlef += a[i] != c;
    lef += a[i];
  }
  for (long long i = a.length() / 2; i < a.length(); i++) {
    drig += a[i] != c;
    rig += a[i];
  }
  return min(dlef + minTocs(rig, (char)c + 1),
             minTocs(lef, (char)c + 1) + drig);
}
int main() {
  testCases = 1;
  cin >> testCases;
  while (testCases--) {
    long long n;
    cin >> n;
    string s;
    cin >> s;
    cout << minTocs(s, 'a') << endl;
  }
  return 0;
}
void simpleSieve(long long N, bool prime[]) {
  long long i, j;
  for (i = 0; i < N + 1; i++) prime[i] = true;
  for (i = 2; i * i <= N; i++) {
    if (prime[i]) {
      for (j = i * i; j <= N; j += i) {
        prime[j] = false;
      }
    }
  }
}
void PrimeDivisorSieve(long long N, long long prime[]) {
  long long i, j;
  for (i = 0; i < N + 1; i++) prime[i] = i;
  for (i = 2; i * i <= N; i++) {
    if (prime[i] == i) {
      for (j = i; j <= N; j += i) {
        if (prime[j] == j) prime[j] = i;
      }
    }
  }
}
void swap(long long &x, long long &y) {
  x ^= y;
  y ^= x;
  x ^= y;
}
bool isPrime(long long n) {
  if (n <= 1) return false;
  for (long long i = 2; i < n; i++)
    if (n % i == 0) return false;
  return true;
}
long long power(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long gcdExtended(long long a, long long b, long long *x, long long *y) {
  if (a == 0) {
    *x = 0, *y = 1;
    return b;
  }
  long long x1, y1;
  long long gcd = gcdExtended(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
long long modInverse(long long b, long long m) {
  long long x, y;
  long long g = gcdExtended(b, m, &x, &y);
  if (g != 1) return -1;
  return (x % m + m) % m;
}
long long modDivide(long long a, long long b, long long m) {
  a = a % m;
  long long inv = modInverse(b, m);
  if (inv == -1)
    return -1;
  else
    return (inv * a) % m;
}

```