#include <bits/stdc++.h>
using namespace std;
class solution
{
public:
    int binary_search(int num, vector<int> &a);
    int LIS_length(vector<int> &nums);
};
int solution::binary_search(int num, vector<int> &a) //二分查找
{
    int low = 0, high = a.size() - 1, mid;
    while (low <= high)
    {
        mid = low + (high - low) / 2;
        if (a[mid] == num)
            return mid;
        else if (a[mid] > num)
            high = mid - 1;
        else if (a[mid] < num)
            low = mid + 1;
    }
    return low;
}

int solution::LIS_length(vector<int> &nums)
{
    vector<int> st;
    if (nums.size() == 0)
        return 0;
    st.push_back(nums[0]);
    for (int i = 1; i < nums.size(); i++)
    {
        if (nums[i] > st.back()) //如果第i个元素是大于st中最后一个元素的则直接加进去
        {
            st.push_back(nums[i]);
        }
        else
        {
            int pos = binary_search(nums[i], st); //若第i个元素是小于栈顶的，直接进行替换
            st[pos] = nums[i];
        }
    }
    return st.size();
}

int main()
{
    solution a;
    int n;
    cin >> n;
    vector<int> s;
    for (int i = 0; i < n; i++)
    {
        s.clear();
        int j;
        cin >> j;
        for (int t = 0; t < j; t++)
        {
            int m;
            cin >> m;
            s.push_back(m);
        }
        cout << a.LIS_length(s)<<" ";
    }
}

#include<bits/stdc++.h>
using namespace std;
class solution
{
    public:
    void  dfs(vector<int> &array, vector<vector<int> >  &s1,vector<vector<int> > &s2,vector<int> &find);
    int binary_search(int num, vector<int> &a);
    void  print_all(vector<int> &array,vector<vector<int> > &s2);
    void  find_allLIS(vector<int> &array);
    
};
int solution::binary_search(int num, vector<int> &a) //二分查找
{
    int low = 0, high = a.size() - 1, mid;
    while (low <= high)
    {
        mid = low + (high - low) / 2;
        if (a[mid] == num)
            return mid;
        else if (a[mid] > num)
            high = mid - 1;
        else if (a[mid] < num)
            low = mid + 1;
    }
    return low;
}
void  solution::dfs(vector<int> &array, vector<vector<int> >  &s1,vector<vector<int> > &s2,vector<int> &find) 
{
	//find即是每一次搜索最长路径的下标保存数组
  int lmax = find.size();
  //s1的长度即是最大长度
	if (s1.size() == lmax) { 
		//搜索数组长度等于最大序列长度时，添加该路径
		s2.push_back(find);
		return;
	}
	for (auto i : s1[lmax]) {
		//添加到搜索队列的条件
		if (find.empty() || find.back() < i && array[find.back()]<array[i]) 
    {
			find.push_back(i);
			dfs(array, s1, s2, find);
			find.pop_back();
		}
	}
}
void  solution::print_all(vector<int> &array,vector<vector<int> > &s2) 
{
	for (auto r : s2) 
  {
		cout << "LIS:";
		for (auto i : r) {
			cout << array[i] << " ";
		}
		cout << endl;
	}
}
void  solution::find_allLIS(vector<int> &array) 
{
	vector<int>  arr;
  vector<int> a;
	vector<vector<int> >  s1; //对该数组所有元素进行一个下标的分类
  int n = array.size();
	for (int i = 0; i < n;i++) 
  {
		int c = array[i];
		if (arr.empty() || arr.back() < c) 
    {
			arr.push_back(c);
      //该类下标传进s1中保存起来，记录新增加元素的下标
      a.push_back(i);
			s1.push_back(a); 
		}
		else //要是比arr中最后一个元素小，则这个新增加的元素下标分到与他同等级的那一类
   {
      int b = binary_search(c,arr);
      s1[b].push_back(i);
		}
    a.clear();
	}
	vector<vector<int> >  s2;//s2就是用来记录所有符合要求的路径
	vector<int>  find;//只是每一次过程当中会用到的数组
	dfs(array, s1, s2, find);
	print_all(array, s2);
}

int main()
{
    solution s;
    vector<int> array;
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        int a;
        cin>>a;
        array.push_back(a);
    }
    s.find_allLIS(array);
}