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").
# ------------------- fast io --------------------
from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase


 
import itertools
 
 
if sys.version_info[0] < 3:
    input = raw_input
    range = xrange
 
    filter = itertools.ifilter
    map = itertools.imap
    zip = itertools.izip
 
    
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")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
 
input = lambda: sys.stdin.readline().rstrip("\r\n")
if os.path.exists('input.txt'):
    sys.stdin = open('input.txt','r')
    sys.stdout = open('output.txt','w')
 
 
# ------------------- fast io --------------------
from math import *
from itertools import * # chain,groupby,permutations,combinations
from collections import *
from bisect import *
from heapq import *
 
 


 
"""
 
def gcd(x, y):
    
    while y:
        x, y = y, x % y
    return x
 
 
def prod(a, mod=10**9+7):
    ans = 1
    for each in a:
        ans = (ans * each) % mod
    return ans
 
def lcm(a, b): return a * b // gcd(a, b)
 
def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y
 
 
def powerset(s):
    n=len(s)
    
    return chain.from_iterable(combinations(s,r) for r in range(1,n))
 
def binarySearch(arr,x): 
    l=0
    r=len(arr)-1
    while l <= r: 
  
        mid = l + (r - l) // 2; 
        if arr[mid] == x: 
            return mid 
        elif arr[mid] < x: 
            l = mid + 1
        else: 
            r = mid - 1
    return -1
 
def prime(n): #array of prime numbers
    arr = [1]*(n+1)
    arr[0] = arr[1] = 0
    p=2
    while p*p<=n:
        if arr[p]:
            for i in range(p * 2, n + 1, p):
                arr[i] = 0
            p+=1
 
 
    return arr

def prime(n):
    # Returns  a list of primes < n 
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]
 
def isprime(x) -> bool: #return true if number is prime
    i=2
    while i*i<=x:
        if x%i==0:
            return 0
        i+=1
    return 1
 
 
def palindrome(string,start,end):
    if start==end:
        return True
    if end==1:
        return True
    return string[start]==string[end-1] and palindrome(string,start+1,end-1)
 
def binomialCoeff(n, k):
 
    
    C = [0 for i in range(k+1)]
    C[0] = 1  
 
    for i in range(1, n+1):
 
        
        j = min(i, k)
        while (j > 0):
            C[j] = C[j] + C[j-1]
            j -= 1
 
    return C[k]
 
"""
 
#----#
 
 

inf = float("inf")
mod = 10**9+7
 
def aa(): #for int
    return int(input())
def bb(): #for int arr
    return list(map(int,input().split()))
def cc():  #for string
    s = input()
    return list(s)
def dd(): #space seperated intege
    return map(int,input().split())
#----#
print("D")

def koi_coding_sikha_do():

    n = aa()
    arr = cc()

    brr = sorted(arr)
    ans=0
    for i in range(n):
        ans+= arr[i]!=brr[i]
    print(ans)

    
            

onlyone = 0
t=1 if onlyone else int(input())
while(t):
    
    koi_coding_sikha_do()
    
    t-=1
 
 
 
"""
 
__________          __  .__                              __    __             _________                          
\______   \___.__._/  |_|  |__   ____   ____             \ \   \ \            \_   ___ \     .__         .__     
 |     ___<   |  |\   __\  |  \ /  _ \ /    \             \ \   \ \           /    \  \/   __|  |___   __|  |___ 
 |    |    \___  | |  | |   Y  (  <_> )   |  \            / /   / /           \     \____ /__    __/  /__    __/ 
 |____|    / ____| |__| |___|  /\____/|___|  /           /_/   /_/             \______  /    |__|        |__|    
           \/                \/            \/                                         \/                         
 
 
Unke aakhon me aasu aur chahre pe hasi hai......lagta hai unki lulli unki zip me phasi hai
"""
 
 
 



    
