Longest Increasing Subsequence

Given an array of integers, your task is to determine the length of the Longest Increasing Subsequence (LIS). A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements.

The LIS of an array is defined as the longest subsequence such that every element in the subsequence is smaller than the ones that come after it. Formally, if the subsequence is represented as \(a_{i_1}, a_{i_2}, \ldots, a_{i_k}\) with \(1 \leq i_1 < i_2 < \ldots < i_k \leq n\), then it satisfies \(a_{i_1} < a_{i_2} < \ldots < a_{i_k}\). Your goal is to compute \(LIS\) for each test case.

Note: Use the \(O(n^2)\) dynamic programming approach as the input constraints are moderate.

inputFormat

The input is given via standard input in the following format:

T
n1
a1 a2 ... an1
n2
b1 b2 ... bn2
... 
nT
c1 c2 ... cnT

Where \(T\) is 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 containing \(n\) space-separated integers.

outputFormat

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

## sample

2
8
10 22 9 33 21 50 41 60
6
3 10 2 1 20 19

5
3

</p>