Longest Alternating Subsequence

You are given an array ‘ARR’ of integers. Your task is to find the length of the longest alternating subsequence.

Note:

A sequence a1, a2, .... an is called an alternating sequence if its elements satisfy one of the following relations : a1 < a2 > a3 < a4 > a5..... or  a1 > a2 < a3 > a4 < a5.

For example:

'ARR' = {3, 10, 1, 2, 30}, the longest alternating subsequence for this array can be {3, 10, 1, 30} or {3, 10, 2, 30}. Therefore, the answer will be 4.

Input format :

The first line of input contains an integer 'T' denoting the number of test cases.

The first line of each test case contains a single integer 'N' representing the length of the array.

The second line of each test case contains 'N' space-separated integers representing the elements of the array 'ARR'.

Output format :

For each test case, return a single integer which is the length of the longest alternating subsequence. 

Print the output of each test case in a separate line.

Note:

You don’t have to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 5000
1 <= ARR[i] <= 10^5

Where 'ARR[i]' denotes the ith element of 'ARR'.

Time limit: 1 sec

Sample Input 1 :

2
7
1 2 5 3 10 15 12
4 
1 4 2 3

Sample Output 1 :

5
4

Explanation of Sample Output 1:

In test case 1, Given 'ARR' = {1,2,5,3,10,15,12}, we can see that the longest alternating subsequence for this array can be {1,5,3,15,12} or {2,5,3,15,12}. Therefore, the length will be 5.

In test case 2, Given 'ARR' = {1,4,2,3} we can see that the longest alternating subsequence for this array will be {1,4,2,3}. Therefore, length will be 4.

Sample Input 2 :

2
5
1 2 3 4 5      
3
1 3 2

Sample Output 2 :

2
3

Explanation of Sample Output 2:

In test case 1, Given 'ARR' = {1,2,3,4,5}, we can see that the longest alternating subsequence for this array can be any pair of two elements. Therefore, the length will be 2.

In test case 2, Given 'ARR' = {1,3,2} we can see that the longest alternating subsequence for this array will be {1,3,2}. Therefore, the length will be 3.