#define _CRT_SECURE_NO_WARNINGS
#include<queue>
#include<cmath>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=500010;
int n,a[N];

struct SegmentTree{
    int maxi[N<<2],mini[N<<1];
#define maxi(x) maxi[x]
#define mini(x) mini[x]

    inline void build(int p,int l,int r)
    {
        if(l==r)return maxi(p)=mini(p)=a[l],void();
        int mid=l+r>>1;
        build(p<<1,l,mid),build(p<<1|1,mid+1,r);
        maxi(p)=max(maxi(p<<1),maxi(p<<1|1));
        mini(p)=min(mini(p<<1),mini(p<<1|1));
    }

    inline void change(int p,int l,int r,int d,int v)
    {
        if(l==r)return maxi(p)=mini(p)=v,void();
        int mid=l+r>>1;
        if(d<=mid)change(p<<1,l,mid,d,v);
        if(d>mid)change(p<<1|1,mid+1,r,d,v);
        maxi(p)=max(maxi(p<<1),maxi(p<<1|1));
        mini(p)=min(mini(p<<1),mini(p<<1|1));
    }

    inline int query(int p,int l,int r,int L,int R,int v,int op) //op==0 min arg(i){a[i]>=v}
    {//op==1 max arg(i){a[i]<=v)
     //   cout<<"query "<<p<<" "<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<v<<" "<<op<<endl;
        if(l==r)
        {
            if(!op)return a[l]>=v?l:-1;
            else return a[l]<=v?l:-1;
        }/**/
        int mid=l+r>>1,res=-1;
        if(!op)
        {
            if(L<=mid&&maxi(p<<1)>=v)res=query(p<<1,l,mid,L,R,v,op);
            if(res==-1)res=query(p<<1|1,mid+1,r,L,R,v,op);
        }
        else
        {
            if(R>mid&&mini(p<<1|1)<=v)res=query(p<<1|1,mid+1,r,L,R,v,op);
            if(res==-1)res=query(p<<1,l,mid,L,R,v,op);
        }
        //if((~res1)&&(~res2))return op?max(res1,res2):min(res1,res2);
        //else return (~res1)?res1:res2;
        return res;
    }
}t;

int ans;
inline int parti(int *a,int l,int r)
{
    int mid=l+r>>1,piv=a[l+r>>1];
//    cout<<"parti "<<l<<" "<<r<<" "<<piv<<endl;;
    for(int i=l-1,j=r+1,ii,jj;;)
    {
        ii=t.query(1,1,n,i+1,n,piv,0);
        jj=t.query(1,1,n,1,j-1,piv,1);
//        cout<<"ii jj "<<ii<<" "<<jj<<endl;
        if(ii>=jj)return jj;
        ans++;swap(a[ii],a[jj]);
        t.change(1,1,n,ii,a[ii]);
        t.change(1,1,n,jj,a[jj]);
        i=ii,j=jj;
    }
}

inline void quisort(int *a,int l,int r)
{
    int p;
    if(l&&r&&l<r)
    {
        p=parti(a,l,r);
        //getchar();
        quisort(a,l,p);
        quisort(a,p+1,r);
        
    }
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        t.build(1,1,n);
        ans=0;
        quisort(a,1,n);
        printf("%d\n",ans);
    }
    return 0;
}