Longest Increasing Path of Planets

You are given a series of test cases. In each test case, you are provided with a sequence of planets, each having an associated energy level. A traveler can visit the planets in the given order and may only move from a planet to a later one if the energy level of the next planet is strictly greater than that of the current one.

Your task is to determine the maximum number of planets the traveler can visit in one journey following this rule. Formally, if the energy levels are represented as \(a_1, a_2, \dots, a_n\), you need to find the length of the longest subsequence \(a_{i_1}, a_{i_2}, \dots, a_{i_k}\) such that \(i_1 < i_2 < \dots < i_k\) and \(a_{i_1} < a_{i_2} < \dots < a_{i_k}\).

This is essentially the classic Longest Increasing Subsequence (LIS) problem solved using dynamic programming.

inputFormat

The input is given via standard input (stdin) and has the following format:

T
n_1
a_{1,1} a_{1,2} ... a_{1,n_1}
...
n_T
a_{T,1} a_{T,2} ... a_{T,n_T}

Here, \(T\) is the number of test cases. For each test case, the first line contains an integer \(n\), the number of planets, followed by a line with \(n\) space-separated integers representing the energy levels of the planets.

outputFormat

For each test case, output a single line containing one integer: the length of the longest increasing path (i.e. the maximum number of planets a traveler can visit following the rule).

## sample

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

3
4
1

</p>