#include <bits/stdc++.h>
using namespace std;
const int N = 1e3;
const long long INF = 1e18;
const long long MOD = 1e9 + 7;
bool m[N];
vector<int> primes(1, 2);
long double nk[N][N];
void sieve() {
  for (int i = 4; i < N; i += 2) m[i] = 1;
  for (int i = 3; i * i <= N; i += 2)
    if (!m[i])
      for (int j = i * i; j < N; j += i) m[j] = 1;
  for (int i = 3; i < N; i += 2)
    if (!m[i]) primes.push_back(i);
}
void pascal() {
  for (int i = (0), ThxMK = (N); i < ThxMK; ++i) nk[i][0] = nk[i][i] = 1.0;
  for (int i = (1), ThxMK = (N); i < ThxMK; ++i)
    for (int j = (1), ThxMK = (i); j < ThxMK; ++j)
      nk[i][j] = nk[i - 1][j - 1] + nk[i - 1][j];
}
long long gcd(long long a, long long b) { return (b ? gcd(b, a % b) : a); }
long long lcm(long long a, long long b) {
  if (a < b) swap(a, b);
  long long c = gcd(a, b);
  a /= c;
  return a * b;
}
int popcount(long long x) { return __builtin_popcountll(x); }
long long poww(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a;
    a = a * a;
    b /= 2;
  }
  return res;
}
long long powm(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % MOD;
    a = (a * a) % MOD;
    b /= 2;
  }
  return res;
}
bool isPrime(long long x) {
  if (x == 1) return 0;
  for (auto i : primes) {
    if (i * i > x) return 1;
    if (x % i == 0) return 0;
  }
  return 1;
}
vector<vector<int> > acum;
long long first(int c, int l, int r) {
  if (r == l) return !((acum[c][r] - acum[c][r - 1]) == 1);
  int mid = (l + r) / 2;
  long long a = mid - l + 1 - (acum[c][mid] - acum[c][l - 1]);
  long long b = mid - l + 1 - (acum[c][r] - acum[c][mid]);
  return min(a + first(c + 1, mid + 1, r), b + first(c + 1, l, mid));
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    string second;
    cin >> second;
    acum = vector<vector<int> >(26, vector<int>(n + 1, 0));
    for (int i = (0), ThxMK = (n); i < ThxMK; ++i) {
      int c = second[i] - 'a';
      acum[c][i + 1] = 1;
    }
    for (int i = (0), ThxMK = (26); i < ThxMK; ++i)
      for (int j = (1), ThxMK = (n + 1); j < ThxMK; ++j)
        acum[i][j] += acum[i][j - 1];
    cout << first(0, 1, n) << '\n';
  }
}

### Prompt

Please provide a Cpp coded solution to the problem described below:

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;
const int N = 1e3;
const long long INF = 1e18;
const long long MOD = 1e9 + 7;
bool m[N];
vector<int> primes(1, 2);
long double nk[N][N];
void sieve() {
  for (int i = 4; i < N; i += 2) m[i] = 1;
  for (int i = 3; i * i <= N; i += 2)
    if (!m[i])
      for (int j = i * i; j < N; j += i) m[j] = 1;
  for (int i = 3; i < N; i += 2)
    if (!m[i]) primes.push_back(i);
}
void pascal() {
  for (int i = (0), ThxMK = (N); i < ThxMK; ++i) nk[i][0] = nk[i][i] = 1.0;
  for (int i = (1), ThxMK = (N); i < ThxMK; ++i)
    for (int j = (1), ThxMK = (i); j < ThxMK; ++j)
      nk[i][j] = nk[i - 1][j - 1] + nk[i - 1][j];
}
long long gcd(long long a, long long b) { return (b ? gcd(b, a % b) : a); }
long long lcm(long long a, long long b) {
  if (a < b) swap(a, b);
  long long c = gcd(a, b);
  a /= c;
  return a * b;
}
int popcount(long long x) { return __builtin_popcountll(x); }
long long poww(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a;
    a = a * a;
    b /= 2;
  }
  return res;
}
long long powm(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % MOD;
    a = (a * a) % MOD;
    b /= 2;
  }
  return res;
}
bool isPrime(long long x) {
  if (x == 1) return 0;
  for (auto i : primes) {
    if (i * i > x) return 1;
    if (x % i == 0) return 0;
  }
  return 1;
}
vector<vector<int> > acum;
long long first(int c, int l, int r) {
  if (r == l) return !((acum[c][r] - acum[c][r - 1]) == 1);
  int mid = (l + r) / 2;
  long long a = mid - l + 1 - (acum[c][mid] - acum[c][l - 1]);
  long long b = mid - l + 1 - (acum[c][r] - acum[c][mid]);
  return min(a + first(c + 1, mid + 1, r), b + first(c + 1, l, mid));
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    string second;
    cin >> second;
    acum = vector<vector<int> >(26, vector<int>(n + 1, 0));
    for (int i = (0), ThxMK = (n); i < ThxMK; ++i) {
      int c = second[i] - 'a';
      acum[c][i + 1] = 1;
    }
    for (int i = (0), ThxMK = (26); i < ThxMK; ++i)
      for (int j = (1), ThxMK = (n + 1); j < ThxMK; ++j)
        acum[i][j] += acum[i][j - 1];
    cout << first(0, 1, n) << '\n';
  }
}

```