Ninja is assigned a task to reach the last stone by his master. These stones are numbered with some value and in the form of an array. He is allowed to jump either odd-numbered jumps or even-numbered jumps and has to reach the last stone.

So your task is to find the number of starting index from which he may start jumping so he reaches the last stones. You are provided with the given array and you have to find the number of starting index of the array from which Ninja can reach the end of the array by jumping some number of times.

For jumping you have to follow below instructions:

You may jump forward from index ‘i’ to index ‘j’ (with i < j) in the following way:

During odd-numbered jumps (i.e., jumps 1, 3, 5, ...), you jump to the index ‘j’ such that ‘arr[i] <= arr[j]’ and ‘arr[j]’ is the smallest possible value. If there are multiple such indices ‘j’, you can only jump to the smallest such index j.

During even-numbered jumps (i.e., jumps 2, 4, 6, ...), you jump to the index ‘j’ such that ‘arr[i] >= arr[j]’ and ‘arr[j]’ is the largest possible value. If there are multiple such indices ‘j’, you can only jump to the smallest such index ‘j’.

It may be the case that for some index ‘i’, there are no legal jumps.

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains a single integer ‘N’ denoting the size of the ‘arr’ array.

The next line contains ‘N’ space-separated integers denoting the values of elements of the ‘arr’ array.

Output Format:

For each test case, print a single line containing the number of starting indices, from where Ninja can reach the end by following the required jump conditions.

The output of each test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 5000
0 <= arr[i] < 10 ^ 6

Where ‘T’ is the number of test cases, ‘N’ is the size of an array, and ‘arr[i]’ represents the elements of the array.

Time Limit: 1 sec