Longest Increasing Subsequence

You are given an array of integers. Your task is to determine the length of the longest subsequence in which the elements are in strictly increasing order.

The input begins with an integer T, representing the number of test cases. Then for each test case, the first line contains an integer N — the number of elements in the array. The next line contains N space-separated integers representing the array's elements.

For each test case, output the length of the longest increasing subsequence.

Recall the longest increasing subsequence (LIS) of a sequence is defined as the longest subsequence of elements which are in strictly increasing order. In mathematical terms, given an array \(a_1, a_2, \dots, a_N\), find the maximum \(k\) such that there exist indices \(i_1 < i_2 < \dots < i_k\) with \(a_{i_1} < a_{i_2} < \dots < a_{i_k}\).

inputFormat

The first line contains a single integer T, the number of test cases. For each test case:

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

outputFormat

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

## sample

2
5
10 22 9 33 21
6
5 8 7 1 9 10

3
4

</p>