Longest Increasing Subsequence

You are given T test cases. For each test case, you are provided with an array of N integers. Your task is to find the length of the longest strictly increasing subsequence in the array.

A subsequence is a sequence that can be derived from the array by removing some or no elements without changing the order of the remaining elements.

The desired property is that for a subsequence A[i₁], A[i₂], ..., A[i_k] where i₁ < i₂ < ... < i_k, the following holds:

\( A[i_1] < A[i_2] < \cdots < A[i_k] \).

For example, if the array is [10, 20, 10, 30, 20, 50], the length of the longest strictly increasing subsequence is 4.

inputFormat

The first line of input contains an integer T, the number of test cases. Each test case is described in two lines:

1. The first line contains an integer N denoting the number of elements in the array.
2. The second line contains N space-separated integers.

If N is zero, there will be no elements on the second line.

outputFormat

For each test case, output a single integer on a new line representing the length of the longest strictly increasing subsequence.

## sample

4
6
10 20 10 30 20 50
4
3 10 2 1
5
1 2 3 4 5
5
9 8 7 6 5

4
2
5
1

</p>