#include <bits/stdc++.h>
using namespace std;
//---------------------------------------------------
#define FOR(i,n)        for(int i=0;i<n;i++)
#define FORab(i,a,b)    for(int i=a;i<b;i++)
//---------------------------------------------------
#define ll              long long
#define pb              push_back
#define pob             pop_back
#define all(x)          x.begin() , x.end()
#define allr(x)         x.rbegin() , x.rend()
#define fi              first
#define sec             second
#define stop            continue;
#define MOD             1000000007
//---------------------------------------------------
#define debug(i , j)    cout<<i<<' '<< j<<'\n';
#define ans(a)          cout<<a<<'\n';
#define cy              cout<<"YES\n";
#define cn              cout<<"NO\n";

int check(int *arr,int i ,int j){
    // debug(i,j)
    // for(int z = 0 ; z < (j-i-1) ; z++){
        // cout<<arr[i+z]<<" "<<arr[i+1+z]<<" "<<arr[i+2+z]<<"\n";
        if( (arr[i] >= arr[i+1] && arr[i+1] >= arr[i+2] ) 
            || (arr[i] <= arr[i+1] && arr[i+1] <= arr[i+2] ) ){
            return 0;
        }

        if( j - i == 3){
            if( (arr[i+1] >= arr[i+2] && arr[i+2] >= arr[i+3] ) 
                || (arr[i+1] <= arr[i+2] && arr[i+2] <= arr[i+3] )
                || (arr[i] >= arr[i+1] && arr[i+1] >= arr[i+3] ) 
                || (arr[i] <= arr[i+1] && arr[i+1] <= arr[i+3] )
                || (arr[i] >= arr[i+2] && arr[i+2] >= arr[i+3] ) 
                || (arr[i] <= arr[i+2] && arr[i+2] <= arr[i+3] ) 
                 ){
                return 0;
            }            
        }

    // }
    return 1;
}

int main() {
    int t;cin>>t;
    while(t--){
        int n;
        cin>>n;
        int arr[n];FOR(i,n)cin>>arr[i];
        // string s;cin>>s;

        int cnt = n + n - 1;

        FOR(i,n-2){
            if( check(arr,i,i+2) ){
              cnt++;
              if(i+3<n && check(arr,i,i+3)) cnt++;
            }
        }

        ans(cnt)
        // ans("-----------------------")
    }
    return 0;
}
### Prompt

Please provide a Cpp coded solution to the problem described below:

Suppose you have two points p = (x_p, y_p) and q = (x_q, y_q). Let's denote the Manhattan distance between them as d(p, q) = |x_p - x_q| + |y_p - y_q|.

Let's say that three points p, q, r form a bad triple if d(p, r) = d(p, q) + d(q, r).

Let's say that an array b_1, b_2, ..., b_m is good if it is impossible to choose three distinct indices i, j, k such that the points (b_i, i), (b_j, j) and (b_k, k) form a bad triple.

You are given an array a_1, a_2, ..., a_n. Calculate the number of good subarrays of a. A subarray of the array a is the array a_l, a_{l + 1}, ..., a_r for some 1 ≤ l ≤ r ≤ n.

Note that, according to the definition, subarrays of length 1 and 2 are good.

Input

The first line contains one integer t (1 ≤ t ≤ 5000) — the number of test cases.

The first line of each test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of array a.

The second line of each test case contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9).

It's guaranteed that the sum of n doesn't exceed 2 ⋅ 10^5.

Output

For each test case, print the number of good subarrays of array a.

Example

Input


3
4
2 4 1 3
5
6 9 1 9 6
2
13 37


Output


10
12
3

Note

In the first test case, it can be proven that any subarray of a is good. For example, subarray [a_2, a_3, a_4] is good since it contains only three elements and: 

  * d((a_2, 2), (a_4, 4)) = |4 - 3| + |2 - 4| = 3 < d((a_2, 2), (a_3, 3)) + d((a_3, 3), (a_4, 4)) = 3 + 1 + 2 + 1 = 7; 
  * d((a_2, 2), (a_3, 3)) < d((a_2, 2), (a_4, 4)) + d((a_4, 4), (a_3, 3)); 
  * d((a_3, 3), (a_4, 4)) < d((a_3, 3), (a_2, 2)) + d((a_2, 2), (a_4, 4)); 



In the second test case, for example, subarray [a_1, a_2, a_3, a_4] is not good, since it contains a bad triple (a_1, 1), (a_2, 2), (a_4, 4): 

  * d((a_1, 1), (a_4, 4)) = |6 - 9| + |1 - 4| = 6; 
  * d((a_1, 1), (a_2, 2)) = |6 - 9| + |1 - 2| = 4; 
  * d((a_2, 2), (a_4, 4)) = |9 - 9| + |2 - 4| = 2; 



So, d((a_1, 1), (a_4, 4)) = d((a_1, 1), (a_2, 2)) + d((a_2, 2), (a_4, 4)).

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
//---------------------------------------------------
#define FOR(i,n)        for(int i=0;i<n;i++)
#define FORab(i,a,b)    for(int i=a;i<b;i++)
//---------------------------------------------------
#define ll              long long
#define pb              push_back
#define pob             pop_back
#define all(x)          x.begin() , x.end()
#define allr(x)         x.rbegin() , x.rend()
#define fi              first
#define sec             second
#define stop            continue;
#define MOD             1000000007
//---------------------------------------------------
#define debug(i , j)    cout<<i<<' '<< j<<'\n';
#define ans(a)          cout<<a<<'\n';
#define cy              cout<<"YES\n";
#define cn              cout<<"NO\n";

int check(int *arr,int i ,int j){
    // debug(i,j)
    // for(int z = 0 ; z < (j-i-1) ; z++){
        // cout<<arr[i+z]<<" "<<arr[i+1+z]<<" "<<arr[i+2+z]<<"\n";
        if( (arr[i] >= arr[i+1] && arr[i+1] >= arr[i+2] ) 
            || (arr[i] <= arr[i+1] && arr[i+1] <= arr[i+2] ) ){
            return 0;
        }

        if( j - i == 3){
            if( (arr[i+1] >= arr[i+2] && arr[i+2] >= arr[i+3] ) 
                || (arr[i+1] <= arr[i+2] && arr[i+2] <= arr[i+3] )
                || (arr[i] >= arr[i+1] && arr[i+1] >= arr[i+3] ) 
                || (arr[i] <= arr[i+1] && arr[i+1] <= arr[i+3] )
                || (arr[i] >= arr[i+2] && arr[i+2] >= arr[i+3] ) 
                || (arr[i] <= arr[i+2] && arr[i+2] <= arr[i+3] ) 
                 ){
                return 0;
            }            
        }

    // }
    return 1;
}

int main() {
    int t;cin>>t;
    while(t--){
        int n;
        cin>>n;
        int arr[n];FOR(i,n)cin>>arr[i];
        // string s;cin>>s;

        int cnt = n + n - 1;

        FOR(i,n-2){
            if( check(arr,i,i+2) ){
              cnt++;
              if(i+3<n && check(arr,i,i+3)) cnt++;
            }
        }

        ans(cnt)
        // ans("-----------------------")
    }
    return 0;
}
```