Longest Increasing Subsequence

Given an array representing the heights of buildings, your task is to determine the length of the longest increasing subsequence (LIS). The longest increasing subsequence is the longest sequence of elements in the array that are in strictly increasing order.

You are required to process multiple test cases. For each test case, you will be provided with the number of buildings followed by the heights of the buildings.

In mathematical terms, if we denote the sequence of heights as \(a_1, a_2, \dots, a_n\), you need to find the maximum \(k\) such that there exists indices \(i_1 < i_2 < \cdots < i_k\) with \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\).

Use an efficient algorithm with a time complexity of \(O(n \log n)\) per test case.

inputFormat

The input is read from standard input (stdin) and is structured as follows:

1. The first line contains a single integer \(T\) denoting the number of test cases.
2. For each test case, the first integer \(n\) is given on a new line, representing the number of buildings.
3. This is followed by a line containing \(n\) space-separated integers representing the heights of the buildings.

outputFormat

For each test case, output a single line containing the length of the longest increasing subsequence. The output should be written to standard output (stdout).

## sample

3
6
5 3 4 8 6 7
5
1 2 2 3 4
4
4 3 2 1

4
4
1

</p>