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").

//package com.company;



import  java.math.*;
import java.util.*;
import java.lang.*;
import java.io.*;



public final class Main {

    FastReader s;


    public static void main (String[] args) throws java.lang.Exception
    {

        new Main().run();

    }
    void run()
    {
        s = new FastReader();
        solve();
    }
   StringBuffer sb;
   // int counter;
    void solve()
    {
         sb = new StringBuffer();

        for(int T = s.nextInt();T > 0;T--)
        {


            start();


        }

       // System.out.print(sb);

    }


    void start()
    {
        int n = s.nextInt();

       String x = s.nextLine();
       String g = sortString(x);
       // System.out.println(x+" "+g);
       int k = 0;
       for(int i = 0; i<x.length(); i++)
       {
              if(x.charAt(i) != g.charAt(i))
                  k++;
       }
        System.out.println(k);

    }
    public static String sortString(String inputString)
    {
        // convert input string to char array
        char tempArray[] = inputString.toCharArray();

        // sort tempArray
        Arrays.sort(tempArray);

        // return new sorted string
        return new String(tempArray);
    }





    long gcd(long a, long b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
    long power(long x, long y, long p)
    {
        long res = 1; // Initialize result

        // Update x if it is more
        // than or equal to p
        x = x % p;

        while (y > 0)
        {
            // If y is odd, multiply
            // x with the result
            if ((y & 1) > 0)
                res = (res * x) % p;

            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }
        return res;
    }

    int lower_bound(int [] arr , int key)
    {

        int i = 0;
        int j = arr.length-1;
          //if(arr[i] > key)return -1;
         if(arr[j] < key)return -1;

        while(i<j)
        {
            int mid = (i+j)/2;

            if(arr[mid] == key)
            {
                j = mid;
            }

            else if(arr[mid] < key)
            {
                i = mid+1;
            }
            else
                j = mid-1;
      }

        return i;
    }

    int upper_bound(int [] arr , int key)
    {

        int i = 0;
        int j = arr.length-1;
        if(arr[j] <= key)return j+1;

        while(i<j)
        {
            int mid = (i+j)/2;



             if(arr[mid] <= key)
            {
                i = mid+1;
            }
            else
                j = mid;
        }

        return i;
    }


    static void sort(int[] A){
        int n = A.length;
        Random rnd = new Random();
        for(int i=0; i<n; ++i){
            int tmp = A[i];
            int randomPos = i + rnd.nextInt(n-i);
            A[i] = A[randomPos];
            A[randomPos] = tmp;
        }
        Arrays.sort(A);
    }
    static void sort(long[] A){
        int n = A.length;
        Random rnd = new Random();
        for(int i=0; i<n; ++i){
            long tmp = A[i];
            int randomPos = i + rnd.nextInt(n-i);
            A[i] = A[randomPos];
            A[randomPos] = tmp;
        }
        Arrays.sort(A);
    }
    static String sort(String s) {
        Character ch[]=new Character[s.length()];
        for(int i=0;i<s.length();i++) {
            ch[i]=s.charAt(i);
        }
        Arrays.sort(ch);
        StringBuffer st=new StringBuffer("");
        for(int i=0;i<s.length();i++) {
            st.append(ch[i]);
        }
        return st.toString();
    }

    //long array input
    public long [] longArr(int len)
    {
        // long arr input
        long [] arr = new long[len];
        String [] strs =  s.nextLine().trim().split("\\s+");
        for(int i =0; i<len; i++)
        {
            arr[i] = Long.parseLong(strs[i]);

        }
        return arr;
    }
    // int arr input
    public int [] intArr(int len)
    {
        // long arr input
        int [] arr = new int[len];
        String [] strs =  s.nextLine().trim().split("\\s+");
        for(int i =0; i<len; i++)
        {
            arr[i] = Integer.parseInt(strs[i]);

        }
        return arr;
    }

    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;
        }
    }



}
