#include <fstream>

#define MAX_N 50000

using namespace std;

int v[MAX_N], t[MAX_N + 1], bestLower[MAX_N + 1], bestVal[MAX_N + 1];

struct AIB {
    int n;
    int aib[MAX_N + 2];

    void init( int x ) {
        int i;

        n = x;

        for ( i = 0; i <= n; i++ )
            aib[i] = 0;
    }

    void update( int i, int x ) {
        while ( i <= n ) {
            aib[i] = max( aib[i], x );
            i += (i & -i);
        }
    }

    int query( int i ) {
        int m;

        m = 0;
        while ( i > 0 ) {
            m = max( m, aib[i] );
            i -= (i & -i);
        }

        return m;
    }
};

AIB len;

int main() {
    ifstream cin( "scmax2.in" );
    ofstream cout( "scmax2.out" );

    int q, n, maxLen, maxLenCrt, i;

    cin >> q;
    while ( q-- ) {
        cin >> n;
        for ( i = 0; i < n; i++ )
            cin >> v[i];

        len.init( n );

        maxLen = 0;
        for ( i = 0; i < n; i++ ) {
            maxLenCrt = max( len.query( v[i] ), bestVal[v[i]] ) + 1;

            len.update( v[i], maxLenCrt );
            bestVal[t[v[i]]] = max( bestVal[t[v[i]]], maxLenCrt );

            maxLen = max( maxLen, maxLenCrt );
        }

        cout << maxLen << "\n";
    }

    return 0;
}