Longest Strictly Increasing Subsequence with a Special Case

You are given t test cases. In each test case you are given a sequence of n integers. If n ≤ 2, output n directly. Otherwise, compute the length of the longest strictly increasing subsequence (LIS) of the sequence.

A sequence A = a₁, a₂, \dots, a_n is said to be strictly increasing if for every index i (with 1 ≤ i < n), the following holds:

[ a_i < a_{i+1} ]

A subsequence is a sequence that can be derived from the original sequence by deleting some or no elements without changing the order of the remaining elements.

Your task is to output, for each test case, the length of the longest strictly increasing subsequence. Note that for sequences of length 2 or less, the answer is defined to be the full length, regardless of whether the sequence is increasing.

inputFormat

The first line contains an integer t, the number of test cases.

For each test case, the input consists of two lines:

• The first line contains an integer n, the length of the sequence.
• The second line contains n space‐separated integers representing the sequence.

You should read input from standard input (stdin).

outputFormat

For each test case, output a single integer, which is the length of the longest strictly increasing subsequence as defined in the problem statement. Each result should be printed on a separate line to standard output (stdout).

## sample

6
5
10 20 30 40 50
6
10 20 20 30 40 50
6
10 30 20 40 50 60
2
10 5
4
1 2 3 4
3
1 1 1

5
5
5
2
4
1

</p>