Non-monotonicity

There is a sequence $A$ of length $n$ made up of the $n$ distinct integers from $1$ to $n$. Among the subsequences of $A$, we want to find the length of the longest sequence $B$ that satisfies the following condition.

$B_0 > B_1 < B_2 > B_3 < \cdots$

That is, reading from left to right the elements of $B$ must alternately satisfy 'greater than, less than, greater than, less than', and the very first comparison must be 'greater than' ($B_0 > B_1$). A subsequence is what remains after deleting zero or more elements from the original sequence, keeping the order of the remaining elements unchanged. A sequence consisting of a single element is also considered to satisfy the condition.

Given $A$, write a program that prints the maximum possible length of $B$.

The first line contains the number of test cases $T$ ($1 \le T \le 50$).

Each test case is given on a single line in the following format.

n A[0] A[1] A[2] ... A[n-1]

Here $n$ is the length of the sequence ($1 \le n \le 30000$), followed by the $n$ elements of $A$ separated by spaces. $A$ is a permutation containing each integer from $1$ to $n$ exactly once.

For each test case, print the maximum length of $B$ on its own line.