Longest Increasing Subsequence

Given a sequence of integers, your task is to determine the length of the longest increasing subsequence (LIS). An increasing subsequence is a sequence extracted from the original sequence where each element is strictly greater than the one before it. The dynamic programming relation can be expressed as: \( dp[i] = \max\left(1,\{dp[j]+1 \mid 0\leq j < i \text{ and } A[j] < A[i]\}\right) \). The final answer is given by \( \max_{0 \leq i < n} dp[i] \).

inputFormat

The input is read from stdin and consists of multiple test cases. The first line contains a single integer T, the number of test cases. Each test case is described by two lines: the first line contains an integer n denoting the number of elements in the sequence, and the second line contains n space-separated integers.

outputFormat

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

3
5
1 2 1 2 3
6
5 1 2 6 3 4
4
7 3 5 3

3
4
2