Longest Increasing Subsequence

Given an array of integers, compute the length of its longest increasing subsequence (LIS). The problem can be formally defined as finding the maximum value of the following recurrence:

\( dp[i] = \max_{0 \leq j < i \; \text{and} \; arr[j] < arr[i]} (dp[j] + 1) \)

If no such \( j \) exists, then \( dp[i] = 1 \). Your task is to process multiple test cases. For each test case, output the length of the longest increasing subsequence.

inputFormat

The first line contains an integer \( T \) indicating the number of test cases. For each test case, the first line contains an integer \( n \) representing the size of the array, followed by a line with \( n \) space-separated integers.

outputFormat

For each test case, output a single integer on a new line which is the length of the longest increasing subsequence of the given array.

## sample

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

3
1

</p>