Longest Increasing Subsequence

You are given several test cases. In each test case, you are provided with an integer n followed by a sequence of n integers. Your task is to compute the length of the longest strictly increasing subsequence of the given sequence.

A subsequence is derived from the sequence by deleting some or no elements without changing the order of the remaining elements. Formally, given a sequence \( a_1, a_2, \dots, a_n \), a subsequence \( a_{i_1}, a_{i_2}, \dots, a_{i_k} \) is called strictly increasing if \( a_{i_1} < a_{i_2} < \dots < a_{i_k} \). Your goal is to find the maximum possible \( k \) for which such a subsequence exists.

Note: Use the stdin for input and stdout for output.

inputFormat

The first line contains an integer T indicating the number of test cases. Each test case is described as follows:

• The first line of each test case contains an integer n denoting the length of the sequence.
• The second line contains n space-separated integers representing the sequence.

It is guaranteed that n is non-negative. If n equals 0, then no integers follow for that test case.

outputFormat

For each test case, output a single integer in a new line representing the length of the longest strictly increasing subsequence.

## sample

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

3
1
3

</p>