22796_Antimonotonicity

I have a sequence Fred of length n comprised of integers between 1 and n inclusive. The elements of Fred are pairwise distinct. I want to find a subsequence Mary of Fred that is as long as possible and has the property that:

Mary₀ > Mary₁ < Mary₂ > Mary₃ < ...

The first line of input will contain a single integer T expressed in decimal with no leading zeroes. T will be at most 50. T test cases will follow.

Each test case contains a single line. A line describing a test case is formatted as follows:

n  Fred₀  Fred₁  Fred₂  ...  Fred_n-1

where n and each element of Fred is an integer expressed in decimal with no leading zeroes. No line will have leading or trailing whitespace, and two adjacent integers on the same line will be separated by a single space. n willbe at most 30000.

For each test case, output a single integer followed by a new line --- the length of the longest subsequence Mary of Fred with the desired properties.

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

1
2
5
3