#include<bits/stdc++.h>
using namespace std;

#define REP(r,x,y) for(register int r=(x); r<(y); r++)
#define PER(r,x,y) for(register int r=(x); r>(y); r--)
#define REPE(r,x,y) for(register int r=(x); r<=(y); r++)
#define PERE(r,x,y) for(register int r=(x); r>=(y); r--)
#ifdef sahdsg
#define DBG(...) printf(__VA_ARGS__)
#else
#define DBG(...) (void)0
#endif

#define MAXN 40007
#define INF 0x3f3f3f3f
int arr[MAXN];
int n;
int dp[MAXN], pd[MAXN];
inline void solve() {
	memset(pd,0x3f,sizeof pd);
	int ans=0;
	REP(i,0,n) {
		int k=lower_bound(pd+1,pd+1+n,arr[i])-pd;
		dp[i]=k; pd[k]=arr[i];
		ans=max(ans,k);
	}
	printf("%d\n", ans);
}
int main() {
	#ifdef sahdsg
	freopen("in.txt", "r", stdin);
	#endif
	int t; scanf("%d", &t);
	while(0<t--) {
		scanf("%d", &n);
		REP(i,0,n) {
			scanf("%d", &arr[i]);
		}
		solve();
	}
	
	return 0;
}