Longest Alternating Subsequence

You are given a sequence of integers representing daily measurements of a plant's height. Your task is to determine the length of the longest subsequence in which the differences between consecutive numbers strictly alternate between increases and decreases.

In other words, if you denote the chosen subsequence as \(a_1, a_2, \dots, a_k\), then for every \(2 \le i \le k-1\), either \(a_{i-1} a_{i+1}\) or \(a_{i-1} > a_i < a_{i+1}\) must hold. It can be proven that the minimum subsequence length is 1 (when the sequence is empty or no alternation is possible).

For example:

• For the sequence [1, 3, 2, 4, 3], the answer is 5.
• For the sequence [2, 2, 2, 2], the answer is 1.
• For the sequence [3, 2, 1, 2, 1, 3], the answer is 5.

inputFormat

The input is read from stdin and has the following format:

T
n
h[1] h[2] ... h[n]
... (repeated for T test cases)

Here, T is the number of test cases. For each test case, the first line contains an integer n (the number of days), and the second line contains n space-separated integers representing the plant's height measurements.

outputFormat

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

The output is written to stdout.

## sample

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

5
1
5

</p>