algospot - lis

//algospot - lis
 
#include <iostream>
#include <vector>
using namespace std;
 
int N;
vector<int> v;
vector<int> cache;
 
void init()
{
    cin >> N;
    v = vector<int>(N);
    cache = vector<int>(N, -1);
    for(int i = 0; i<N; ++i)
        cin >> v[i];
}
 
int dp(int idx)
{
    int& ret = cache[idx];
    if(ret != -1)
        return ret;
    ret = 0;
    for(int i = idx+1; i<N; ++i)
        if(v[idx] < v[i])
            ret = max(ret, dp(i));
    ++ret;
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int C; cin >> C;
    for(int tn = 0; tn<C; ++tn)
    {
        init();
        int ans = 0;
        for(int i = 0; i<N; ++i)
            ans = max(ans, dp(i));
        cout << ans << "\n";
    }
}