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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.io.*;
import java.util.*;
import java.text.DecimalFormat;
import java.math.*;

public class Main {

static int  mod = 1000000007;
/*****************code By Priyanshu *******************************************/ 

    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;
        }
    }
    // this > other return +ve
    // this < other return -ve
    // this == other return 0
     public static class Pair implements Comparable<Pair> {
      long st;
      long et;

      public Pair(long st, long et) {
         this.st = st;
         this.et = et;
      }

      public int compareTo(Pair other) {
         if (this.st != other.st) {
            return (int)(this.st - other.st);
         } else {
            return (int)(this.et - other.et);
         }
      }
   }

    static long fastPower(long a, long b, int n) {
            
            long res = 1;
            
            while ( b > 0) {
                
                if ( (b&1) != 0) {
                    res = (res * a % n) % n;
                }
                
                a = (a % n * a % n) % n;
                b =  b >> 1;
            }
            
            return res;
            
        }

     // function to find
    // the rightmost set bit
    static int PositionRightmostSetbit(int n)
    {
        // Position variable initialize
        // with 1 m variable is used to
        // check the set bit
        int position = 1;
        int m = 1;
 
        while ((n & m) == 0) {
 
            // left shift
            m = m << 1;
            position++;
        }
        return position;
    }
    
         // used for swapping ith and jth elements of array
      // public static void swap(int[] arr, int i, int j) {
      //   int temp = arr[i];
      //   arr[i] = arr[j];
      //   arr[j] = temp;
      // }
        public static void swap(long i, long j) {
        long temp = i;
        i = j;
        j = temp;
      }


    static boolean palindrome(String s) {
        return new StringBuilder(s).reverse().toString().equals(s);
    }
    
  static boolean isPerfectSquare(double x)
    {
            double sr = Math.sqrt(x);
            return ((sr * sr) == x);     
    }


 public static long gcd(long a, long b)
    {
      if (b == 0)
        return a;
      return gcd(b, a % b);
    }
    
   

   static int nod(long l) {
       if(l>=1000000000000000000l) return 19;
       if(l>=100000000000000000l) return 18;
       if(l>=10000000000000000l) return 17;
       if(l>=1000000000000000l) return 16;
       if(l>=100000000000000l) return 15;
       if(l>=10000000000000l) return 14;
       if(l>=1000000000000l) return 13;
       if(l>=100000000000l) return 12;
       if(l>=10000000000l) return 11;
       if(l>=1000000000) return 10;
       if(l>=100000000) return 9;
       if(l>=10000000) return 8;
       if(l>=1000000) return 7;
       if(l>=100000) return 6;
       if(l>=10000) return 5;
       if(l>=1000) return 4;
       if(l>=100) return 3;
       if(l>=10) return 2;
       return 1;
    }
      //Arrays.sort(a,(c,d) -> Integer.compare(c[0],d[0]));

    
    public static boolean areAllBitsSet(int n )
    {
        // all bits are not set
        if (n == 0)
            return false;
     
        // if true, then all bits are set
        if (((n + 1) & n) == 0)
            return true;
     
        // else all bits are not set
        return false;
    }

     public static long[] sort(long[] arr) {
        List<Long> temp = new ArrayList();
        for (long i : arr) temp.add(i);
        Collections.sort(temp);
        int start = 0;
        for (long i : temp) arr[start++] = i;
        return arr;
    }
   
 

        public static int[] radixSort2(int[] a)
    {
        int n = a.length;
        int[] c0 = new int[0x101];
        int[] c1 = new int[0x101];
        int[] c2 = new int[0x101];
        int[] c3 = new int[0x101];
        for(int v : a) {
            c0[(v&0xff)+1]++;
            c1[(v>>>8&0xff)+1]++;
            c2[(v>>>16&0xff)+1]++;
            c3[(v>>>24^0x80)+1]++;
        }
        for(int i = 0;i < 0xff;i++) {
            c0[i+1] += c0[i];
            c1[i+1] += c1[i];
            c2[i+1] += c2[i];
            c3[i+1] += c3[i];
        }
        int[] t = new int[n];
        for(int v : a)t[c0[v&0xff]++] = v;
        for(int v : t)a[c1[v>>>8&0xff]++] = v;
        for(int v : a)t[c2[v>>>16&0xff]++] = v;
        for(int v : t)a[c3[v>>>24^0x80]++] = v;
        return a;
    } 

  


 


    public static void main(
        String[] args)
    {
        try {
            System.setIn(new FileInputStream("input.txt"));
            System.setOut(new PrintStream(new FileOutputStream("output.txt")));
        } catch (Exception e) {
            System.err.println("Error");
        }
         
       FastReader sc = new FastReader();
        int t = Integer.parseInt(sc.next());
      // int t = 1;
       // StringBuilder ans = new StringBuilder();
        
   while(t-->0){
        int n = sc.nextInt();
      //  long k = sc.nextLong();

        char a[] = sc.next().toCharArray();

        char b[] = new char[a.length];

        for(int i = 0;i<a.length;i++){
                b[i] = a[i];
        }

        Arrays.sort(a);

            int c = 0;
         for(int i = 0;i<a.length;i++){
                if(b[i] != a[i]){
                    c++;
                }
        }

        System.out.println(c);




        
           
    }
  }
}
//code By Priyanshu 
