Ilya lives in the beautiful city of Bytes lying in a hilly terrain. She loves to ride her bicycle on the hills whenever she gets a chance to do so.

There are check-posts located on the hill at a unit distance from each other. The height of the check posts is given in an array A.
Ilya has to visit her aunt who lives N check-posts away.
Being a hilly area, the terrain in between the check-posts is either monotonically increasing or decreasing. She is initially standing at checkpoint indexed 1.
However, Ilya suffers from a rare sleeping disorder in which she goes to sleep while riding her bicycle if the terrain is uniform. She wakes up whenever there is a change in nature of terrain i.e from increasing to decreasing or from decreasing to increasing.
You have been given an easy task of counting number of times Ilya wakes up during her sleep as she passes through these N check-posts falling on the way to her aunt's house. 

Note

You can safely assume that the terrain between i^th and (i + 1)^th checkpoint will be uniform i.e it will have either increasing slope or decreasing slope.

It is guaranteed that no two adjacent check-posts have same heights.

Input

The first line of the input contains an integer T denoting the number of test cases.
The first line of the test case consists of an integer N denoting the number of check-posts.
The first line of each test case contains a single integer N denoting the number of check-posts. The second line contains N space-separated integers A1, A2, ..., AN denoting the heights of check-posts falling on the way.

Output

For each test case, output a single integer denoting number of times Ilya wakes up from her sleep in a separate line .

Constraints

1 ≤ T ≤ 10
2 ≤ N ≤ 10^5
-10^9 ≤ Ai ≤ 10^9

Example
Input:
2
3
1 3 2
5
1 2 3 4 5
Output:
1
0

Explanation
Example case 1. She wakes up when the height changes from 3 to 2
Example case 2. She never wakes up in between the sleep

见题面

见题面