Longest Increasing Subsequence

You are given an array of integers. Your task is to compute the length of the longest subsequence that is strictly increasing. A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

Formally, given an array \(a_1, a_2, \dots, a_n\), find the maximum integer \(L\) such that there exist indices \(1 \le i_1 < i_2 < \dots < i_L \le n\) with \(a_{i_1} < a_{i_2} < \dots < a_{i_L}\).

This problem is a classic application of dynamic programming.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
n_1
a_11 a_12 ... a_1n
n_2
a_21 a_22 ... a_2n
... 
n_T
a_T1 a_T2 ... a_Tn

Where:

• T is the number of test cases.
• For each test case, the first line contains an integer n (the size of the array), followed by a line containing n space-separated integers.

outputFormat

For each test case, output a single line to standard output (stdout) containing the length of the longest strictly increasing subsequence for the given array.

## sample

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

4
3
1

</p>