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").
#!/usr/bin/env python

'''

//////////////////////////////////////////////////
//                                              //
//                                              //
//          C++ Competitive Programming         //
//              Template by Cyberkid            //
//                                              //
//            Meet my Codechef Doggie           //
//                                              //
//      |\_/|                                   //
//      | @ @   Woof!                           //
//      |   <>              _                   //
//      |  _/\------____ ((| |))                //
//      |               `--' |                  //
//  ____|_       ___|   |___.'                  //
// /_/_____/____/_______|                       //
//                                              //
//   I am here to guard this code, woof!        //
//   Name : Cyberkid05 | Country : India        //
//   Site: Codechef | Contest: Practice Mode    //
//                                              //
//                                              //
//////////////////////////////////////////////////

'''

from __future__ import division, print_function
import io, os, sys, math
from io import BytesIO, IOBase

# input = raw_input
# alphabets = "abcdefghijklmnopqrstuvwxyz"

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

def truncate(f, n):
    return math.floor(f * 10 ** n) / 10 ** n

def gcdsmall(a, b):
    while(b):
        a, b = b, a % b
    return a

def gcdbig(a, b):
    if (a == 0):
        return b
    if (b == 0):
        return a
    k = 0
    while(((a | b) & 1) == 0):
        a = a >> 1
        b = b >> 1
        k = k + 1
    while ((a & 1) == 0):
        a = a >> 1
    while(b != 0):
        while ((b & 1) == 0):
            b = b >> 1
        if (a > b):
            temp = a
            a = b
            b = temp
        b = (b - a)
    return (a << k)

def lcm(a, b):
    return int(a * b / gcdsmall(a, b))  # for small numbers
    return int(a * b / gcdbig(a, b))    # for large numbers

def compEvenOdd(a):
    return a % 2 == 0

def main():
    # YOUR CODE HERE
    for _ in range(int(input())):
        res = 0
        sz = int(input())
        word = input()
        word2 = "".join(sorted(word))
        # print(word, word2)
        # print(len(word), len(word2))
        for i in range(sz):
            # print(word[i], word2[i])
            if word[i] != word2[i]:
                res = res + 1
        sys.stdout.write(str(res) + "\n")


# region fastio

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")

if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# end region

if __name__ == "__main__":
    main()