Longest Increasing Subsequence After Removal

You are given an array of n integers. Your task is to remove exactly one element from the array and then determine the length of the longest strictly increasing subsequence (LIS) from the remaining array.

Recall that a subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. A strictly increasing subsequence is one where every element is greater than its previous element.

Your goal is to choose the removal that maximizes the length of the resulting longest increasing subsequence.

Note: If the array contains at most two elements, the answer is defined to be 1.

The answer should be computed by testing the result after removing each possible element.

inputFormat

The first line contains an integer T representing the number of test cases. For each test case, the first line contains an integer n (the number of elements in the array), followed by a line with n space-separated integers denoting the array elements.

outputFormat

For each test case, output a single line containing a single integer: the maximum length of the longest strictly increasing subsequence obtained after removing exactly one element.

## sample

4
5
3 10 2 1 20
6
3 2 6 5 4 5
4
1 2 3 4
5
5 4 3 2 1

3
3
3
1

</p>