LIS(DP)

#include <bits/stdc++.h>
using namespace std;
int n,a[1005];

int fun(int i,int prev,int len)
{
    if(i==n)
       return len;
       
    if(prev==-1)
      return max(fun(i+1,i,len+1),fun(i+1,prev,len));
    
    if(a[i]>a[prev])
      return max(fun(i+1,i,len+1),fun(i+1,prev,len));
    else
      return fun(i+1,prev,len);
    
}

int dp_fun()
{
    int dp[n];
    
    for(int i=0;i<n;i++)
    {
        int maxi=INT_MIN;
        
        for(int j=i-1;j>=0;j--)
        {
            if(a[i]>a[j])
            maxi=max(maxi,dp[j]);
        }
        
        if(maxi==INT_MIN)
           dp[i]=1;
        else
           dp[i]=1+maxi;
    }
    
    return *max_element(dp,dp+n);
}


int main() {
	
	int t; cin>>t;
	while(t--)
	{
	    cin>>n;
	    for(int i=0;i<n;i++)
	    {
	        cin>>a[i];
	    }
	    
	    cout<<dp_fun()<<endl;
	}
	
	
	
	
	return 0;
}