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").
import java.util.*;
import java.io.*;
public class Solution
{
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }
    //static final long mod=(long)1e9+7;
    static final long mod=998244353L;
    public static long pow(long a,long p)
    {
        long res=1;
        while(p>0)
        {
            if(p%2==1)
            {
                p--;
                res*=a;
                res%=mod;
            }
            else
            {
                a*=a;
                a%=mod;
                p/=2;
            }
        }
        return res;
    }
    static class Pair
    {
        int u,v;
        Pair(int u,int v)
        {
            this.u=u;
            this.v=v;
        }
    }
    /*static class Pair implements Comparable<Pair>
    {
        int v,l;
        Pair(int v,int l)
        {
            this.v=v;
            this.l=l;
        }
        public int compareTo(Pair p)
        {
            return l-p.l; 
        }
    }*/
    static long gcd(long a,long b)
    {
        if(b%a==0)
        return a;
        return gcd(b%a,a);
    }
    public static class comp implements Comparator<Pair>
    {
        public int compare(Pair p1,Pair p2)
        {
            if(p1.v>p2.v)
            return 1;
            return -1;
        }
    }
    public static void main(String args[])throws Exception
    {
        FastReader fs=new FastReader();
        PrintWriter pw=new PrintWriter(System.out);
        int tc=fs.nextInt();
        while(tc-->0)
        {
            int n=fs.nextInt();
            char c[]=fs.nextLine().toCharArray();
            char c1[]=new char[n];
            for(int i=0;i<n;i++)
            c1[i]=c[i];
            Arrays.sort(c1);
            int cnt=0;
            for(int i=0;i<n;i++)
            {
                if(c1[i]!=c[i])
                cnt++;
            }
            pw.println(cnt);
        }
        pw.flush();
        pw.close();
    }
}