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.lang.*;
import java.io.*;
import java.math.*;


public class CODEFORCES {
     static HashMap<Integer, Integer> sortByValue(HashMap<Integer, Integer> hm)
    {
        // Create a list from elements of HashMap
        List<Map.Entry<Integer, Integer> > list =
               new LinkedList<Map.Entry<Integer, Integer> >(hm.entrySet());
 
        // Sort the list
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer> >() {
            public int compare(Map.Entry<Integer, Integer> o1,
                               Map.Entry<Integer, Integer> o2)
            {
                return (o1.getValue()).compareTo(o2.getValue());
            }
        });
         
        // put data from sorted list to hashmap
        HashMap<Integer, Integer> temp = new LinkedHashMap<Integer, Integer>();
        for (Map.Entry<Integer, Integer> aa : list) {
            temp.put(aa.getKey(), aa.getValue());
        }
        return temp;
    }
    static class FastReader {
        byte[] buf = new byte[2048];
        int index, total;
        InputStream in;
 
        FastReader(InputStream is) {
            in = is;
        }
 
        int scan() throws IOException {
            if (index >= total) {
                index = 0;
                total = in.read(buf);
                if (total <= 0) {
                    return -1;
                }
            }
            return buf[index++];
        }
 
        String next() throws IOException {
            int c;
            for (c = scan(); c <= 32; c = scan())
                ;
            StringBuilder sb = new StringBuilder();
            for (; c > 32; c = scan()) {
                sb.append((char) c);
            }
            return sb.toString();
        }
 
        String nextLine() throws IOException {
            int c;
            for (c = scan(); c <= 32; c = scan())
                ;
            StringBuilder sb = new StringBuilder();
            for (; c != 10 && c != 13; c = scan()) {
                sb.append((char) c);
            }
            return sb.toString();
        }
 
        char nextChar() throws IOException {
            int c;
            for (c = scan(); c <= 32; c = scan())
                ;
            return (char) c;
        }
 
        int nextInt() throws IOException {
            int c, val = 0;
            for (c = scan(); c <= 32; c = scan())
                ;
            boolean neg = c == '-';
            if (c == '-' || c == '+') {
                c = scan();
            }
            for (; c >= '0' && c <= '9'; c = scan()) {
                val = (val << 3) + (val << 1) + (c & 15);
            }
            return neg ? -val : val;
        }
 
        long nextLong() throws IOException {
            int c;
            long val = 0;
            for (c = scan(); c <= 32; c = scan())
                ;
            boolean neg = c == '-';
            if (c == '-' || c == '+') {
                c = scan();
            }
            for (; c >= '0' && c <= '9'; c = scan()) {
                val = (val << 3) + (val << 1) + (c & 15);
            }
            return neg ? -val : val;
        }
 
    }
 static void print(int h){
          System.out.println(h);
 } 
    public static void main(String[] args) throws java.lang.Exception {
      FastReader sc=new FastReader(System.in);
        int w=sc.nextInt();
        for(int g=0;g<w;g++) {
            
           int size=sc.nextInt();
       String s=sc.next();
       char[] a=s.toCharArray();
       int max=0;   int max2=0;
       int cnt=0;
       for(int i=0;i<size-1;i++){
           if(a[i]>a[i+1])
            max2=-1;
           if(a[i]<=a[i+1])cnt++;
           else{
              
               if(cnt>max)max=cnt;
               cnt=0;
           }
       }
       if(max2==0)print(0);
       else{
            if(cnt>max)max=cnt;
      
          print(size-max);
       }
       	         
       
	         
	    
                
}
}
}



// 1 1 0 2 3 2 2 1 3 3
// 4 2 1 3
// 1
// 0 0 1 1 0 1 1 1 0 1 1 1 0
// 2 1 2 2 1 1 1 1 2 1 0 2 2
// 1 1 3 2 1 3 3 1 2 2 3 2 0

// 1 1 2 3 0 1 2 2 3 3 
// 1 2 3 4 
// 1 
// 1 1 1 0 1 1 1 1 0 0 0 1 0 
// 1 1 1 2 1 1 2 1 2 2 0 2 2 
// 1 3 2 1 1 3 2 3 2 2 3 0 1 











       //   Arrays.sort(arr);
            //   for(int i=0;i<size-1;i++){
            //       if(arr[i]==arr[i+1]){
            //           if(count==1){
            //               varr=i;
            //           }
            //           count++;
            //       }else{
            //           if(count>=k){
            //               for(int j=varr;j<=i;j++){
            //                     if(m>k){
            //                      arr3[i]=0;  
            //                   }
            //                   arr3[j]=m;
            //                   m++;
                              
            //               }
                           
            //           }
            //           count=1;
            //       }
            //   }
            //     for(int i=0;i<size;i++){
            //         if(arr[i]==-1){
            //             count3++;
            //         }
            //     }
            //     m=1;
            //  int ff=count3/k;
            //   for(int ii=0;ii<ff;ii++){
            //     for(int i=0;i<size;i++){
            //         if(arr[i]==-1){
            //             if(m>k)break;
            //             arr[i]=m;
            //             m++;
            //         }
            //     } 
            //     m=0;
            //     }
            //   for(int i=0;i<size;i++){
            //       if(arr3[i]==-1){
            //           arr3[i]=0;
            //       }
            //   }
            //   for(int i=0;i<size;i++){
            //      System.out.print(arr3[i]+" ");
            //   }System.out.println();









 // static long lcm(long a, long b) {
    //     return (a / gcd(a, b)) * b;
    // }
    // static long gcd(long a, long b) {
    //     if(a==0) return b;
 
    //     return gcd(b%a,a);
    // }
    // static void premutation(int n, ArrayList<Integer> arr,boolean[] chosen) {
    //     if(arr.size() == n) {
    //         System.out.println(arr);
    //     }else {
    //         for(int i=1; i<=n; i++) {
    //             if(chosen[i]) continue;
    //             arr.add(i);
    //             chosen[i] = true;
    //             premutation(n,arr,chosen);
    //             arr.remove(new Integer(i));
    //             chosen[i] = false;
    //         }
    //     }
    // }
    // public static ArrayList<Integer> sieveOfEratosthenes(int n) {
    //     // Create a boolean array
    //     // "prime[0..n]" and
    //     // initialize all entries
    //     // it as true. A value in
    //     // prime[i] will finally be
    //     // false if i is Not a
    //     // prime, else true.
    //     boolean prime[] = new boolean[n + 1];
    //     for (int i = 0; i <= n; i++)
    //         prime[i] = true;
 
    //     for (int p = 2; p * p <= n; p++) {
    //         // If prime[p] is not changed, then it is a
    //         // prime
    //         if (prime[p] == true) {
    //             // Update all multiples of p
    //             for (int i = p * p; i <= n; i += p)
    //                 prime[i] = false;
    //         }
    //     }
    //     ArrayList<Integer> arr = new ArrayList<>();
    //     // Print all prime numbers
    //     for (int i = 2; i <= n; i++) {
    //         if (prime[i] == true)
    //             arr.add(i);
    //     }
    //     return arr;
    // }
    // static int countDigit(long n) {
    //     String number= Long.toString(n);
    //     return number.length();
    // }
    // static boolean isPalindrome(char[] c) {
    //     int n = c.length;
    //     for(int i=0; i<n/2; i++) {
    //         if(c[i] != c[n-i-1]) return false;
    //     }
    //     return true;
    // }
    // static long nCk(int n, int k) {
    //     return (modMult(fact(n),fastexp(modMult(fact(n-k),fact(k)),M-2)));
    // }
    // static long fact (long n) {
 
    //     long fact =1;
    //     for(int i=1; i<=n; i++) {
    //         fact = modMult(fact,i);
    //     }
    //     return fact%M;
    // }
    // static int modMult(long a,long b) {
    //     return (int) (a*b%M);
    // }
    // static int negMult(long a,long b) {
    //     return (int)((a*b)%M + M)%M;
    // }
    // static long fastexp(long x, int y){
    //     if(y==1) return x;
 
    //     long ans = fastexp(x,y/2);
    //     if(y%2 == 0) return modMult(ans,ans);
    //     else return modMult(ans,modMult(ans,x));
    // }
    // static final Random random = new Random();
    // static void ruffleSort(int[] arr){
    //     int n = arr.length;
    //     for(int i=0; i<n; i++)
    //     {
    //         int j = random.nextInt(n);
    //         int temp = arr[j];
    //         arr[j] = arr[i];
    //         arr[i] = temp;
    //     }
    //     Arrays.sort(arr);
    // }
    // static boolean isPrime(int n) {
    //     if (n <= 1) return false;
    //     if (n <= 3) return true;
    //     if (n % 2 == 0 || n % 3 == 0) return false;
    //     for (int i = 5; i * i <= n; i = i + 6)
    //         if (n % i == 0 || n % (i + 2) == 0)
    //             return false;
    //     return true;
    // }
    // public static class Pairs implements Comparable<Pairs> {
    //     int f,s;
    //     Pairs(int f, int s)
    //     {
    //         this.f = f;
    //         this.s = s;
    //     }
    //     public int compareTo(Pairs p)
    //     {
    //         if(this.f != p.f) return Integer.compare(this.f,p.f);
    //         return  Integer.compare(this.s,p.s);
    //     }
 
    //     @Override
    //     public boolean equals(Object o) {
    //         if (this == o) return true;
    //         if (!(o instanceof Pairs)) return false;
    //         Pairs pairs = (Pairs) o;
    //         return f == pairs.f && s == pairs.s;
    //     }
 
    //     @Override
    //     public int hashCode() {
    //         return Objects.hash(f, s);
    //     }
    // }
//   while(j<s_arr.length&&t_arr[i]!=s_arr[j]){
//                     j++;
//               }
//             if(j==s_arr.length){
//                   System.out.println("NO");
//             }else{
//                 //  System.out.println(i);//0
//                 //   System.out.println(j);//2
//                     i++;
                    
//               int count=0;
//                 int temp2=-1;
//                 int temp=-1;
//                             int temp3=-1;
//                                         int temp4=-1;
//                 boolean doing=true;
//          while(i!=t_arr.length&&j<s_arr.length){
//                 if(j<(s_arr.length-1)&&i<t_arr.length&&t_arr[i]==s_arr[j+1]){
//                     temp=j;
                   
//                     j++; 
                 
//                     temp2=i;
//                     i++;
//                     doing=false;
                   
//                 }
//                 else if(j<s_arr.length&&j>0&&t_arr[i]==s_arr[j-1]){
//                     temp3=i;
//                     temp4=j;
//                           while(i!=t_arr.length&&j<s_arr.length){
                              
//                              if(j<s_arr.length&&j>0&&t_arr[i]==s_arr[j-1]){
//                                  j--;
//                                  i++;
//                               }else{
//                                   break;
//                               } 
//                           }
//                           if(i!=t_arr.length){
//                               i=temp3;
//                               j=temp4;
                               
//                           }
//                           doing=false;
//                 }
//                 if(temp>=0&&temp2>=0&&temp<s_arr.length&&temp>0&&t_arr[temp2]==s_arr[temp-1]){
//                         int y=temp2;
                            
//                         while(y!=t_arr.length){
                      
//                              if(temp<s_arr.length&&temp>0&&t_arr[y]==s_arr[temp-1]){
//                                  temp--;
//                                  y++;
//                               }else{
//                                   break;
//                               }
//                         }
//                       if(y==t_arr.length){
//                           i=y;
//                           break;
//                       }
                      
//                       doing=false;
//                   }
//                 if(doing==true){
//                     j++;
//                     i=0;
//                 }
//                 doing=true;
             
//             }
//         if(i==t_arr.length){
//                 System.out.println("YES");
//             }else{
//                   System.out.println("NO");
//             }
//             }
    