import java.util.*;
import java.io.*;

public class Main
{
    static Scanner sc = new Scanner( System.in );
    
    public static void main( String[] ksc ) throws Exception
    {
        int t = sc.nextInt();
        while( t-- > 0 ) solve();
    }
    
    private static void solve() throws Exception
    {
        int n = sc.nextInt();
        long cnt = 0, val = 0;
        Queue< r > arr = new LinkedList<>();
        
        for( int i = 0; i < n; i++ )
        {
            long key = sc.nextLong();
            if( val != key )
            {
                if( cnt != 0 ) arr.add( new r( val, cnt ) );
                val = key;
                cnt = 1;
            } else cnt++;
        }
        arr.add( new r( val, cnt ) );
        long sum = 0;
        PriorityQueue< r > pq = new PriorityQueue<>();
        int t = arr.size();
        for( int i = 0; i < t; i++ )
        {
            r key = arr.poll();
            pq.add( key );
            if( !(pq.isEmpty() || pq.peek().v > key.v) )
            {
                while( pq.peek().v >= key.v )
                {
                    if(pq.size() < 2) break;
                    r pop = pq.poll();
                    r update = pq.poll();
                    update = new r( update.v, update.c + pop.c );
                    pq.add( update );
                    sum += pop.c;
                }
            }
        }
        
        
        while( pq.size() > 1 )
        {
            r pop = pq.poll();
            r update = pq.poll();
            update = new r( update.v, update.c + pop.c );
            pq.add( update );
            sum += pop.c;
        }
        
        System.out.println( sum );
    }
    
    static class r implements Comparable< r >
    {
        long c, v;
        
        r( long v, long c )
        {
            this.v = v;
            this.c = c;
        }
        
        @Override
        public int compareTo( r o )
        {
            return (int) ( ( this.v - o.v ) % 195329 );
        }
    }
}