Longest Increasing Subsequence

You are given an array of n integers. Your task is to determine the length of the longest increasing subsequence (LIS) in the array. An increasing subsequence is a sequence of numbers such that each element is greater than the previous one. For example, in the array \( [5, 8, 3, 7, 9, 1] \), one of the longest increasing subsequences is \( [5, 7, 9] \) with a length of 3.

Note: The subsequence is not required to be contiguous in the original array.

The problem should be solved by reading input from stdin and writing the answer to stdout.

inputFormat

The first line of input contains an integer T representing the number of test cases.
For each test case, the first line contains an integer N representing the number of elements in the array.
The second line contains N space-separated integers, which are the elements of the array.

Example:

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

outputFormat

For each test case, print a single integer on a new line representing the length of the longest increasing subsequence of the provided array.

Example:

3
1

## sample

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

3
1

</p>