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.*;
import java.lang.reflect.Array;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;



public class copy{
    public static int find(int a,int[] parent)
    {
        if(parent[a]==-1)
            return a;
        return find(parent[a],parent);
    }

    public static void union(int a,int b,int[] parent, int[] rank)
    {
        int x=find(a,parent);
        int y=find(b,parent);
        if(rank[x]>rank[y])
            parent[y]=x;
        else if(rank[y]>rank[x])
            parent[x]=y;
        else
        {
            parent[x]=y;
            rank[y]++;
        }
    }

    static double answer;

    public static int check(ArrayList<ArrayList<Integer>> edges,int x,int parent,int[] statues,int n)
    {
        ArrayList<Integer> arr=new ArrayList<>();
        for(int i:edges.get(x))
        {
            if(i!=parent)
            {
                arr.add(check(edges,i,x,statues,n));
            }
        }
        int sum=0;
        for(int i=arr.size()-1;i>=0;i--)
        {

            answer+=((long)arr.get(i)*(long)sum*(long)statues[x])/((double)n*(double)(n-1));
            sum+=arr.get(i);
        }
        answer+=((long)sum*(long)statues[x])/((double)n*(double)(n-1));
        //System.out.println(x+" "+sum);
        return 1+sum;
    }

    public static boolean check(int X,int a,int b)
    {
        System.out.println(X);

        if(X==1)
            return true;
        boolean status=false;
        if(X%a==0 && a!=1)
            status=status || check(X/a,a,b);
        if(X-b>=1 && b!=0)
            status=status || check(X-b,a,b);

        return status;


    }

    public static int check(long xor,ArrayList<Long> sum,int low,int N)
    {
        int l=low;
        int r=N-1;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(sum.get(mid)==xor)
            {
                return mid;
            }
            else
                r=mid-1;
        }

        return 0;
    }

    public static void merge(int l,int mid,int r,cp[] arr,HashMap<Integer,Integer> before)
    {
        int N=mid-l+1,M=r-mid;
        cp[] arr1=new cp[mid-l+1];
        cp[] arr2=new cp[r-mid];
        cp[] arr3=new cp[N+M];
        for(int i=l;i<=mid;i++)
            arr1[i-l]=arr[i];
        for(int i=mid+1;i<=r;i++)
            arr2[i-mid-1]=arr[i];
        int left=0,right=0,k=0;
        while(left<N && right<M)
        {

            if(arr1[left].a<arr2[right].a)
            {
                arr3[k++]=arr1[left++];
            }
            else
            {

                before.put(arr2[right].b,before.getOrDefault(arr2[right].b,0)+N-left);
                count+=N-left;
                arr3[k++]=arr2[right++];
            }
        }

        while(left<N)
        {
            arr3[k++]=arr1[left++];
        }

        while(right<M)
        {
            arr3[k++]=arr2[right++];
        }

        for(int i=l;i<=r;i++)
            arr[i]=arr3[i-l];



    }

    public static void inv(HashMap<Integer,Integer> before,int l,int r,cp[] arr)
    {
        if(l==r)
            return;
        int mid=(l+r)/2;
        inv(before,l,mid,arr);
        inv(before,mid+1,r,arr);
        merge(l,mid,r,arr,before);
    }
    static long count=0;
    public static int check(ArrayList<Long> arr,long X,int low,int N,long mod)
    {
        int l=low;
        int r=N;
        while(l<=r)
        {
            int mid=l+(r-l)/2;
            if(((arr.get(mid)-arr.get(low-1)))/(long)(mid-low+1)<X)
            {
                if(mid+1<=N &&  ((arr.get(mid+1)-arr.get(low-1)))/(long)(mid-low+2)<X)
                    l=mid+1;
                else
                    return mid;
            }
            else
                r=mid-1;
        }

        return -1;
    }

    static int[] visited;
    static int c;


    public static void main(String[] args)throws IOException
    {
        Reader.init(System.in);
        BufferedWriter output=new BufferedWriter(new OutputStreamWriter(System.out));
        int T=Reader.nextInt();
        for(int m=1;m<=T;m++)
        {
        int N=Reader.nextInt();
        String s=Reader.next();
        char[] ch=new char[N];
        for(int i=0;i<N;i++)
            ch[i]=s.charAt(i);
        Arrays.sort(ch);
        int c=0;
        for(int i=0;i<N;i++)
            if(s.charAt(i)!=ch[i])
                ++c;

            output.write(c+"\n");

        }

        output.flush();
    }
}

class cord
{
    int x,y;
    cord(int x1,int y1)
    {
        x=x1;
        y=y1;
    }
}

class cp
{
    int a,b;
    cp(int a,int b)
    {
        this.a=a;
        this.b=b;

    }
}

class sort_cp implements Comparator<cp>
{
    public int compare(cp o1,cp o2)
    {
        if(o1.b>o2.b)
            return -1;
        else if(o1.b<o2.b)
            return 1;
        else
            return 0;
    }
}
class g_node{
    int val;
    long wt;

    g_node(int val, long wt)
    {
        this.val = val;
        this.wt = wt;
    }
}
class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }

    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(
                    reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}
