#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5+10, maxm = 5e3+10, inf = 1e9;
 
int n, t;
int a[maxn];
int tree[4*maxn];
int dp[maxn][2]; 
pair < int, int > p[maxn];
// int t[maxm][maxm];
// string s;
// string a, b, c;

void init(int l, int r, int node) {

    if (l == r) {

        tree[node] = 0;
        return;

    }

    int mid = (l+r)/2;
    init(l, mid, 2*node);
    init(mid+1, r, 2*node+1);

    tree[node] = max(tree[2*node], tree[2*node+1]);

}

void update(int l, int r, int node, int query_ix, int query_val) {
    
    if (l == r) {
        
        tree[node] = query_val;
        return;

    }

    int mid = (l+r)/2;
    if (query_ix <= mid) update(l, mid, 2*node, query_ix, query_val);
    else update(mid+1, r, 2*node+1, query_ix, query_val);

    tree[node] = max(tree[2*node], tree[2*node+1]);

}

int query(int l, int r, int node, int query_ix) {
    
    if (r <= query_ix) return tree[node];

    int mid = (l+r)/2, ans = query(l, mid, 2*node, query_ix);
    if (mid+1 <= query_ix) ans = max(ans, query(mid+1, r, 2*node+1, query_ix));

    return ans;

}

int one[maxn];
ifstream fin("stairway.in");
ofstream fout("stairway.out");

void reset() {

    for (int i = 1 ; i <= n ; ++i)
        dp[i][0] = dp[i][1] = one[i] = 0;

}

void solve() {

    for (int i = 1 ; i <= n ; ++i)
        p[i] = {a[i], i};
    sort(p+1, p+1+n);

    int cnt = 0;
    for (int i = 1 ; i <= n ; ++i) 
        a[p[i].second] = cnt += (p[i].first != p[i-1].first);

    init(0, n, 1);

    int ans = 0;
    for (int i = 1 ; i <= n ; ++i) {

        if (one[a[i]] != 0) dp[i][1] = one[a[i]]+1;
        one[a[i]] = dp[i][0] = query(0, n, 1, a[i]-1)+1;
        update(0, n, 1, a[i], dp[i][1]);

        ans = max(ans, dp[i][1]);

    }

    fout << ans << '\n';

}

void fast_io() {
 
    ios_base :: sync_with_stdio(0);
    fin.tie(nullptr);
    fout.tie(nullptr);
 
}
 
void read() {
 
    fin >> n;
    for (int i = 1 ; i <= n ; ++i)
        fin >> a[i];
 
}
 
signed main () {
 
    fast_io();
    
    fin >> t;
    while (t--) {
        
        reset();
        read();
        solve();
    
    }
 
    return 0;
 
}