#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
ll i,j,p,q,n,m,k,t,a[100006],ans;
ll b[100006],f[100006];
pair <ll,ll> pa[100006];
void read()
{
	freopen("stairway.in","r",stdin);
    freopen("stairway.out","w",stdout);
}
ll rsq (ll k) {
    ll sum=0;
	while (k>=0) {
		sum=max(sum,f[k]);
		k=(k&(k+1)) - 1;
	}
	return sum;
}
void update (ll k, ll d) {

	while (k<100001) {
		f[k]=max(f[k],d);
		k=k|(k+1);
	}
}
void solve()
{
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
        pa[i].first=a[i];
        pa[i].second=i;
    }
    sort(pa+1,pa+n+1);j=0;ans=1;
    for(i=1;i<=n;i++)
    {
        if(pa[i].first!=pa[i-1].first)
            j++;
        a[pa[i].second]=j;
    }/**
    for(i=1;i<=n;i++)
        cout<<a[i]<<" ";
    cout<<endl;*/
    memset(f,0,sizeof(f));
    memset(b,-1,sizeof(b));
    for(i=1;i<=n;i++)
    {
        if(b[a[i]]!=-1)
        {
            p=b[a[i]];
            update(a[i],p+1);
            //cout<<p+1<<" gornoro "<<endl;
        }
        p=rsq(a[i]-1);
        //cout<<p+1<<" dolnoto "<<endl;
        ans=max(ans,p+1);
        b[a[i]]=max(b[a[i]],p+1);
    }
    ans=rsq(100000);
    cout<<ans<<endl;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	read();
	cin>>t;
	while(t--)
	{
        solve();
	}
	return 0;
}