Longest Increasing Subsequence

You are given an array of integers. Your task is to calculate the length of the longest strictly increasing subsequence (LIS) in the array. An increasing 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, such that each element is greater than its preceding element.

The mathematical formulation is: Given an array \(a_1, a_2, \ldots, a_n\), find the maximum \(k\) such that there exists indices \(1 \leq i_1 < i_2 < \ldots < i_k \leq n\) with \(a_{i_1} < a_{i_2} < \ldots < a_{i_k}\).

If the array is empty, the result is 0.

inputFormat

The input is given via standard input (stdin). The first line contains an integer (T), the number of test cases. Each test case consists of two lines. The first line contains an integer (n) representing 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 on standard output (stdout) containing the length of the longest increasing subsequence.## sample

1
9
10 22 9 33 21 50 41 60 80

6