Longest Increasing Subsequence

You are given a list of distinct integers. Your task is to compute the length of the longest strictly increasing subsequence (LIS) in the list.

A subsequence is a sequence that can be derived from the list by deleting some or no elements without changing the order of the remaining elements. The problem can be formulated by the recurrence relation:

$$ lis[i] = \max_{0 \leq j < i \,\text{and}\, a[j] < a[i]} (lis[j]) + 1 $$

The challenge is to implement an efficient algorithm to solve this problem for multiple test cases using the input from standard input (stdin) and printing the output to standard output (stdout).

inputFormat

The input begins with an integer T representing the number of test cases. Each test case consists of two lines:

• The first line contains an integer N, the number of elements in the array.
• The second line contains N space-separated integers.

If N is 0, the array is empty and the output should be 0.

outputFormat

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

## sample

4
6
10 22 9 33 21 50
5
3 10 2 1 20
5
1 2 3 4 5
5
5 4 3 2 1

4
3
5
1

</p>