#include <bits/stdc++.h>
using namespace std;
#define D(x) cout << #x << " " << x << endl
const int MAXN = 200005;
vector<int> dp; //Almacena los elementos
int CeilIndex(vector<int>& v, int l, int r, int key) {
while (r - l > 1) {
int m = l + (r - l) / 2;
if (v[m] >= key)
r = m;
else
l = m;
}
return r;
}
int LongestIncreasingSubsequenceLength(vector<int>& v) {
if (v.size() == 0)
return 0;
vector<int> tail(v.size(), 0);
int length = 1;
tail[0] = v[0];
for (size_t i = 1; i < v.size(); i++) {
if (v[i] < tail[0])
tail[0] = v[i];
else if (v[i] > tail[length - 1])
tail[length++] = v[i];
else
tail[CeilIndex(tail, -1, length - 1, v[i])] = v[i];
}
return length;
}
int main() {
int t, n;
cin >> t;
while(t--) {
cin >> n;
vector<int> arr(n);
for(int i = 0; i < n; ++i) cin >> arr[i];
reverse(arr.begin(), arr.end());
int lisL = LongestIncreasingSubsequenceLength(arr);
cout << lisL << endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBEKHgpIGNvdXQgPDwgI3ggPDwgIiAiIDw8IHggPDwgZW5kbApjb25zdCBpbnQgTUFYTiA9IDIwMDAwNTsKdmVjdG9yPGludD4gZHA7IC8vQWxtYWNlbmEgbG9zIGVsZW1lbnRvcwoKaW50IENlaWxJbmRleCh2ZWN0b3I8aW50PiYgdiwgaW50IGwsIGludCByLCBpbnQga2V5KSB7CiAgICB3aGlsZSAociAtIGwgPiAxKSB7CiAgICAgICAgaW50IG0gPSBsICsgKHIgLSBsKSAvIDI7CiAgICAgICAgaWYgKHZbbV0gPj0ga2V5KQogICAgICAgICAgICByID0gbTsKICAgICAgICBlbHNlCiAgICAgICAgICAgIGwgPSBtOwogICAgfQogCiAgICByZXR1cm4gcjsKfQogCmludCBMb25nZXN0SW5jcmVhc2luZ1N1YnNlcXVlbmNlTGVuZ3RoKHZlY3RvcjxpbnQ+JiB2KSB7CiAgICBpZiAodi5zaXplKCkgPT0gMCkKICAgICAgICByZXR1cm4gMDsKIAogICAgdmVjdG9yPGludD4gdGFpbCh2LnNpemUoKSwgMCk7CiAgICBpbnQgbGVuZ3RoID0gMTsKIAogICAgdGFpbFswXSA9IHZbMF07CiAgICBmb3IgKHNpemVfdCBpID0gMTsgaSA8IHYuc2l6ZSgpOyBpKyspIHsKIAogICAgICAgIGlmICh2W2ldIDwgdGFpbFswXSkKICAgICAgICAgICAgdGFpbFswXSA9IHZbaV07CiAKICAgICAgICBlbHNlIGlmICh2W2ldID4gdGFpbFtsZW5ndGggLSAxXSkKICAgICAgICAgICAgdGFpbFtsZW5ndGgrK10gPSB2W2ldOwogCiAgICAgICAgZWxzZQogICAgICAgICAgICB0YWlsW0NlaWxJbmRleCh0YWlsLCAtMSwgbGVuZ3RoIC0gMSwgdltpXSldID0gdltpXTsKICAgIH0KIAogICAgcmV0dXJuIGxlbmd0aDsKfQoKaW50IG1haW4oKSB7CglpbnQgdCwgbjsKCWNpbiA+PiB0OwoJd2hpbGUodC0tKSB7CgkJY2luID4+IG47CgkJdmVjdG9yPGludD4gYXJyKG4pOwoJCWZvcihpbnQgaSA9IDA7IGkgPCBuOyArK2kpIGNpbiA+PiBhcnJbaV07CgkJcmV2ZXJzZShhcnIuYmVnaW4oKSwgYXJyLmVuZCgpKTsKCQlpbnQgbGlzTCA9IExvbmdlc3RJbmNyZWFzaW5nU3Vic2VxdWVuY2VMZW5ndGgoYXJyKTsKCQljb3V0IDw8IGxpc0wgPDwgZW5kbDsKCX0KCXJldHVybiAwOwp9