Longest Increasing Subsequence

You are given an array of integers. Your task is to find the length of the longest increasing subsequence (LIS) of the array. An increasing subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order, and where each element is strictly greater than its preceding element.

For example, given the array [5, 8, 3, 7, 9, 1], one of the longest increasing subsequences is [5, 7, 9] with a length of 3.

The problem requires you to process multiple test cases. The input will be provided via standard input (stdin) and you should output your results to standard output (stdout). Use the optimal approach you can to ensure your solution passes all test cases.

The mathematical definition for the longest increasing subsequence can be given by:

\[ LIS(i) = \max_{0 \leq j < i \, \text{and}\, A[j] < A[i]} \{LIS(j)\} + 1 \]

where \(A[i]\) is the current element of the array.

inputFormat

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

Each test case is described as follows:

• The first line contains an integer n, representing the size of the array.
• The second line contains n space-separated integers, the elements of the array.

Note: In case n is 0, the second line will be empty, representing an empty array.

outputFormat

For each test case, output a single line containing the length of the longest increasing subsequence for the given array.

## sample

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

3
5
1

</p>