#include <bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = std::pair<int, int>;
template <typename T>
static inline T gcd(T a, T b) {
  a = std::abs(a);
  b = std::abs(b);
  while (b > 0) {
    a %= b;
    std::swap(a, b);
  }
  return a;
}
template <typename T>
static inline T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
template <typename T>
static inline T sqr(T a) {
  return a * a;
}
template <typename T>
static inline bool remin(T &a, const T &val) {
  if (a > val) {
    a = val;
    return true;
  }
  return false;
}
template <typename T>
static inline bool remax(T &a, const T &val) {
  if (a < val) {
    a = val;
    return true;
  }
  return false;
}
static inline ll nxt() {
  int64_t first;
  scanf("%" PRId64, &first);
  return first;
}
static inline void skipEndLine() {
  char c = getchar();
  while (c != '\n') {
    c = getchar();
  }
}
static inline std::string nxtLine() {
  std::string ret;
  char c = '\n';
  while (true) {
    c = getchar();
    if (c == '\n' || c == '\r' || c == -1) {
      break;
    }
    ret.push_back(c);
  }
  return ret;
}
static inline std::string nxtString() {
  std::string ret;
  char c = '\n';
  while (true) {
    c = getchar();
    if (!isspace(c)) {
      break;
    }
  }
  if (c == -1) {
    return ret;
  }
  ret.push_back(c);
  while (true) {
    c = getchar();
    if (isspace(c) || c == -1) {
      break;
    }
    ret.push_back(c);
  }
  return ret;
}
static std::chrono::system_clock::time_point clock_t0;
static inline void init_time() { clock_t0 = std::chrono::system_clock::now(); }
static inline double get_time() {
  auto t = std::chrono::system_clock::now();
  return std::chrono::duration<double>((t - clock_t0)).count();
}
static inline void print_time(const std::string &name) {
  std::cerr << name << " " << get_time() << "s." << std::endl;
}
template <class T>
static inline T pw(T a, ll n) {
  T ret = T(1);
  while (n > 0) {
    if (n & 1) ret = ret * a;
    a = a * a;
    n >>= 1;
  }
  return ret;
}
static inline ll pw(ll a, ll n, ll m) {
  a %= m;
  ll ret = 1;
  while (n > 0) {
    if (n & 1) ret = ret * a % m;
    a = a * a % m;
    n >>= 1;
  }
  return ret;
}
class ThreadPool {
 public:
  ThreadPool(size_t);
  template <class F, class... Args>
  auto enqueue(F &&f, Args &&...args)
      -> std::future<typename std::result_of<F(Args...)>::type>;
  ~ThreadPool();

 private:
  std::vector<std::thread> workers;
  std::queue<std::function<void()> > tasks;
  std::mutex queue_mutex;
  std::condition_variable condition;
  bool stop;
};
inline ThreadPool::ThreadPool(size_t threads) : stop(false) {
  for (size_t i = 0; i < threads; ++i) {
    auto f = [this] {
      for (;;) {
        std::function<void()> task;
        {
          std::unique_lock<std::mutex> lock(this->queue_mutex);
          this->condition.wait(
              lock, [this] { return this->stop || !this->tasks.empty(); });
          if (this->stop && this->tasks.empty()) return;
          task = std::move(this->tasks.front());
          this->tasks.pop();
        }
        task();
      }
    };
    workers.emplace_back(f);
  }
}
template <class F, class... Args>
auto ThreadPool::enqueue(F &&f, Args &&...args)
    -> std::future<typename std::result_of<F(Args...)>::type> {
  using return_type = typename std::result_of<F(Args...)>::type;
  auto task = std::make_shared<std::packaged_task<return_type()> >(
      std::bind(std::forward<F>(f), std::forward<Args>(args)...));
  std::future<return_type> res = task->get_future();
  {
    std::unique_lock<std::mutex> lock(queue_mutex);
    if (stop) {
      throw std::runtime_error("enqueue on stopped ThreadPool");
    }
    tasks.emplace([task]() { (*task)(); });
  }
  condition.notify_one();
  return res;
}
inline ThreadPool::~ThreadPool() {
  {
    std::unique_lock<std::mutex> lock(queue_mutex);
    stop = true;
  }
  condition.notify_all();
  for (std::thread &worker : workers) {
    worker.join();
  }
}
struct pair_hash {
  template <class T1, class T2>
  std::size_t operator()(const std::pair<T1, T2> &p) const {
    auto h1 = std::hash<T1>{}(p.first);
    auto h2 = std::hash<T2>{}(p.second);
    return h1 * 31 + h2;
  }
};
static const ld PI = acosl(-1.0);
static std::mt19937_64 generator{123123123};
using namespace std;
void prepare() {}
void solve(int test) {
  int n = nxt();
  string s = nxtString();
  string t = s;
  sort((t).begin(), (t).end());
  int k = 0;
  for (int(i) = 0; (i) < int(s.length()); ++(i)) {
    k += s[i] != t[i];
  }
  cout << k << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  init_time();
  prepare();
  int t = 1;
  t = nxt();
  for (int i = 0; i < t; ++i) {
    solve(i + 1);
  }
  print_time("Time:");
  return 0;
}

### Prompt

Generate a Cpp solution to the following problem:

A string s of length n, consisting of lowercase letters of the English alphabet, is given.

You must choose some number k between 0 and n. Then, you select k characters of s and permute them however you want. In this process, the positions of the other n-k characters remain unchanged. You have to perform this operation exactly once.

For example, if s="andrea", you can choose the k=4 characters "a_d_ea" and permute them into "d_e_aa" so that after the operation the string becomes "dneraa".

Determine the minimum k so that it is possible to sort s alphabetically (that is, after the operation its characters appear in alphabetical order).

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases. Then t test cases follow.

The first line of each test case contains one integer n (1 ≤ n ≤ 40) — the length of the string.

The second line of each test case contains the string s. It is guaranteed that s contains only lowercase letters of the English alphabet.

Output

For each test case, output the minimum k that allows you to obtain a string sorted alphabetically, through the operation described above.

Example

Input


4
3
lol
10
codeforces
5
aaaaa
4
dcba


Output


2
6
0
4

Note

In the first test case, we can choose the k=2 characters "_ol" and rearrange them as "_lo" (so the resulting string is "llo"). It is not possible to sort the string choosing strictly less than 2 characters.

In the second test case, one possible way to sort s is to consider the k=6 characters "_o__force_" and rearrange them as "_c__efoor_" (so the resulting string is "ccdeefoors"). One can show that it is not possible to sort the string choosing strictly less than 6 characters.

In the third test case, string s is already sorted (so we can choose k=0 characters).

In the fourth test case, we can choose all k=4 characters "dcba" and reverse the whole string (so the resulting string is "abcd").

### Response

```cpp
#include <bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = std::pair<int, int>;
template <typename T>
static inline T gcd(T a, T b) {
  a = std::abs(a);
  b = std::abs(b);
  while (b > 0) {
    a %= b;
    std::swap(a, b);
  }
  return a;
}
template <typename T>
static inline T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
template <typename T>
static inline T sqr(T a) {
  return a * a;
}
template <typename T>
static inline bool remin(T &a, const T &val) {
  if (a > val) {
    a = val;
    return true;
  }
  return false;
}
template <typename T>
static inline bool remax(T &a, const T &val) {
  if (a < val) {
    a = val;
    return true;
  }
  return false;
}
static inline ll nxt() {
  int64_t first;
  scanf("%" PRId64, &first);
  return first;
}
static inline void skipEndLine() {
  char c = getchar();
  while (c != '\n') {
    c = getchar();
  }
}
static inline std::string nxtLine() {
  std::string ret;
  char c = '\n';
  while (true) {
    c = getchar();
    if (c == '\n' || c == '\r' || c == -1) {
      break;
    }
    ret.push_back(c);
  }
  return ret;
}
static inline std::string nxtString() {
  std::string ret;
  char c = '\n';
  while (true) {
    c = getchar();
    if (!isspace(c)) {
      break;
    }
  }
  if (c == -1) {
    return ret;
  }
  ret.push_back(c);
  while (true) {
    c = getchar();
    if (isspace(c) || c == -1) {
      break;
    }
    ret.push_back(c);
  }
  return ret;
}
static std::chrono::system_clock::time_point clock_t0;
static inline void init_time() { clock_t0 = std::chrono::system_clock::now(); }
static inline double get_time() {
  auto t = std::chrono::system_clock::now();
  return std::chrono::duration<double>((t - clock_t0)).count();
}
static inline void print_time(const std::string &name) {
  std::cerr << name << " " << get_time() << "s." << std::endl;
}
template <class T>
static inline T pw(T a, ll n) {
  T ret = T(1);
  while (n > 0) {
    if (n & 1) ret = ret * a;
    a = a * a;
    n >>= 1;
  }
  return ret;
}
static inline ll pw(ll a, ll n, ll m) {
  a %= m;
  ll ret = 1;
  while (n > 0) {
    if (n & 1) ret = ret * a % m;
    a = a * a % m;
    n >>= 1;
  }
  return ret;
}
class ThreadPool {
 public:
  ThreadPool(size_t);
  template <class F, class... Args>
  auto enqueue(F &&f, Args &&...args)
      -> std::future<typename std::result_of<F(Args...)>::type>;
  ~ThreadPool();

 private:
  std::vector<std::thread> workers;
  std::queue<std::function<void()> > tasks;
  std::mutex queue_mutex;
  std::condition_variable condition;
  bool stop;
};
inline ThreadPool::ThreadPool(size_t threads) : stop(false) {
  for (size_t i = 0; i < threads; ++i) {
    auto f = [this] {
      for (;;) {
        std::function<void()> task;
        {
          std::unique_lock<std::mutex> lock(this->queue_mutex);
          this->condition.wait(
              lock, [this] { return this->stop || !this->tasks.empty(); });
          if (this->stop && this->tasks.empty()) return;
          task = std::move(this->tasks.front());
          this->tasks.pop();
        }
        task();
      }
    };
    workers.emplace_back(f);
  }
}
template <class F, class... Args>
auto ThreadPool::enqueue(F &&f, Args &&...args)
    -> std::future<typename std::result_of<F(Args...)>::type> {
  using return_type = typename std::result_of<F(Args...)>::type;
  auto task = std::make_shared<std::packaged_task<return_type()> >(
      std::bind(std::forward<F>(f), std::forward<Args>(args)...));
  std::future<return_type> res = task->get_future();
  {
    std::unique_lock<std::mutex> lock(queue_mutex);
    if (stop) {
      throw std::runtime_error("enqueue on stopped ThreadPool");
    }
    tasks.emplace([task]() { (*task)(); });
  }
  condition.notify_one();
  return res;
}
inline ThreadPool::~ThreadPool() {
  {
    std::unique_lock<std::mutex> lock(queue_mutex);
    stop = true;
  }
  condition.notify_all();
  for (std::thread &worker : workers) {
    worker.join();
  }
}
struct pair_hash {
  template <class T1, class T2>
  std::size_t operator()(const std::pair<T1, T2> &p) const {
    auto h1 = std::hash<T1>{}(p.first);
    auto h2 = std::hash<T2>{}(p.second);
    return h1 * 31 + h2;
  }
};
static const ld PI = acosl(-1.0);
static std::mt19937_64 generator{123123123};
using namespace std;
void prepare() {}
void solve(int test) {
  int n = nxt();
  string s = nxtString();
  string t = s;
  sort((t).begin(), (t).end());
  int k = 0;
  for (int(i) = 0; (i) < int(s.length()); ++(i)) {
    k += s[i] != t[i];
  }
  cout << k << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  init_time();
  prepare();
  int t = 1;
  t = nxt();
  for (int i = 0; i < t; ++i) {
    solve(i + 1);
  }
  print_time("Time:");
  return 0;
}

```