Longest Increasing Subsequence

Your task is to find the length of the longest strictly increasing subsequence (LIS) in a given sequence of numbers. The subsequence does not need to be contiguous, but the order must be maintained.

For each test case, you are provided an integer n followed by a sequence of n integers. You need to output the length of the LIS for that sequence.

The solution should read from standard input (stdin) and write the answer to standard output (stdout).

You can use efficient methods such as binary search combined with dynamic programming to solve the problem.

All formulas are provided in LaTeX format. For example, a sequence A = [a₁, a₂, \dots, a_n] has a LIS whose length L can be computed via:

\( L = \max\{\text{length}(S): S \subseteq A \text{ and } S \text{ is strictly increasing}\} \)

inputFormat

The first line contains an integer T representing the number of test cases.

Each test case consists of two lines:

• The first line contains an integer n, the length of the sequence.
• The second line contains n space-separated integers.

It is guaranteed that n ≥ 0. For an empty sequence, n will be 0.

outputFormat

For each test case, output a single line with the length of the longest strictly increasing subsequence.

## sample

2
5
10 9 2 5 3
6
0 1 0 3 2 3

2
4

</p>