Longest Increasing Subsequence

You are given an array of integers. Your task is to determine the length of the Longest Increasing Subsequence (LIS) of the array. An increasing subsequence is a sequence obtained by deleting some or no elements without changing the order of the remaining elements, such that every element in the subsequence is strictly greater than its preceding element.

Formally, given an array \(A = [a_1, a_2, \dots, a_n]\), find the maximum \(k\) for which there exists indices \(1 \leq i_1 < i_2 < \dots < i_k \leq n\) satisfying \[ a_{i_1} < a_{i_2} < \cdots < a_{i_k} \]

You need to process multiple test cases.

inputFormat

The first line contains an integer \(T\) denoting 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 next line contains \(n\) space separated integers.

outputFormat

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

## sample

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

2
4

</p>