
//Bridging signals 1631 最长上升子序列 dp问题 2010.8.13
#include<iostream>
using namespace std;
const int MAXP=40005;
int L[MAXP];
int bSearch(int left,int right,int num)
{
if(right==left)
return left;
int mid=(left+right)/2;
if(num==L[mid])
return mid;
else if(num>L[mid])
{
if(right<mid+1)
return mid;
else
return bSearch(mid+1,right,num);
}
else if(num<L[mid]) { if(left>mid-1)
return mid;
else
return bSearch(left,mid,num);
}
else return mid;
}
int solve(int n)
{
int ans=0;
int temp=0;
int count=0;
scanf("%d",&temp);
L[ans++]=temp;
n--;
while(n--)
{
scanf("%d",&temp);
if(temp>L[ans-1])
L[ans++]=temp;
else
L[bSearch(0,ans-1,temp)]=temp;
}
return ans;
}
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>n;
cout<<solve(n)<<endl;
}
return 0;
}