#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<ll> vll;
typedef vector <vll> vvll;
typedef pair <ll,ll> pll;
typedef vector <pll> vpll;
 
#define fi first 
#define se second 
#define mp make_pair 
#define pb push_back
#define newl '\n'
#define gcd __gcd
#define forl(i,k,n) for(ll i=k;i<n;i++)
#define fore(i,k,n) for(ll i=k;i<n;i++)
#define revg(i,k,n) for(ll i=k;i>n;i--)
#define reve(i,k,n) for(ll i=k;i>n;i--)
#define MOD 1000000007 //10^9 + 7
#define all(x) x.begin(),x.end()

 
ll INF = 1000000000000000005LL;
 
ll power(ll x, ll y, ll p=MOD){ //positive y
    ll res = 1;
    x = x % p; 
    while (y > 0) { 
        if (y & 1) 
            res = (res*x) % p; 
        y = y>>1; // y = y/2 
        x = (x*x) % p;   
    } 
    return res; 
} 
 
ll inverse(ll a,ll m=MOD){
    return power(a,m-2,m);
}


namespace oneVal
{
    template<typename T>
    void print(T a,T b)
    {
        for(;a!=b;a++)
        {
            cout<<(*a)<<' ';
        }
        cout<<'\n';
    }
}

namespace twoVal
{
    template<typename T>
    void print(T a,T b)
    {
        for(;a!=b;a++)
        {
            cout<<(*a).first<<' '<<(*a).second<<'\n';
        }
    }
    
    
}

bool chk(ll i,ll j,ll k,vll &a)
{
    ll val1 = abs(i-k)+abs(a[i]-a[k]);
    ll val2 = abs(j-k)+abs(a[j]-a[k]);
    ll val3 = abs(i-j)+abs(a[i]-a[j]);
    
    return ((val1==val2+val3) || (val2==val3+val1) || (val3 == val1+val2) );
        
}

void solve() 
{
    ll n;cin>>n;
    
    vll a(n);
    
    forl(i,0,n)cin>>a[i];
    
    ll ans = n+(n-1);
    
    forl(i,0,n-2)
    {
        if(chk(i,i+1,i+2,a)==false)
            ans++;
    }
    
    forl(i,0,n-3)
    {
        bool chk1 = false;
        chk1 |= chk(i,i+1,i+2,a);
        chk1 |= chk(i+1,i+2,i+3,a);
        chk1 |= chk(i,i+2,i+3,a);
        chk1 |= chk(i,i+1,i+3,a);
        if(chk1==false)
            ans++;
    }
    cout<<ans<<'\n';
    
} 


int main() {
    
    //fastio
    ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
    
	ll t=1;
	cin>>t;
	
	while(t--)
	{
	    solve();
	}//while(t--)...ends

	return 0;
}

### Prompt

Please formulate a CPP solution to the following problem:

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 <iostream>
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<ll> vll;
typedef vector <vll> vvll;
typedef pair <ll,ll> pll;
typedef vector <pll> vpll;
 
#define fi first 
#define se second 
#define mp make_pair 
#define pb push_back
#define newl '\n'
#define gcd __gcd
#define forl(i,k,n) for(ll i=k;i<n;i++)
#define fore(i,k,n) for(ll i=k;i<n;i++)
#define revg(i,k,n) for(ll i=k;i>n;i--)
#define reve(i,k,n) for(ll i=k;i>n;i--)
#define MOD 1000000007 //10^9 + 7
#define all(x) x.begin(),x.end()

 
ll INF = 1000000000000000005LL;
 
ll power(ll x, ll y, ll p=MOD){ //positive y
    ll res = 1;
    x = x % p; 
    while (y > 0) { 
        if (y & 1) 
            res = (res*x) % p; 
        y = y>>1; // y = y/2 
        x = (x*x) % p;   
    } 
    return res; 
} 
 
ll inverse(ll a,ll m=MOD){
    return power(a,m-2,m);
}


namespace oneVal
{
    template<typename T>
    void print(T a,T b)
    {
        for(;a!=b;a++)
        {
            cout<<(*a)<<' ';
        }
        cout<<'\n';
    }
}

namespace twoVal
{
    template<typename T>
    void print(T a,T b)
    {
        for(;a!=b;a++)
        {
            cout<<(*a).first<<' '<<(*a).second<<'\n';
        }
    }
    
    
}

bool chk(ll i,ll j,ll k,vll &a)
{
    ll val1 = abs(i-k)+abs(a[i]-a[k]);
    ll val2 = abs(j-k)+abs(a[j]-a[k]);
    ll val3 = abs(i-j)+abs(a[i]-a[j]);
    
    return ((val1==val2+val3) || (val2==val3+val1) || (val3 == val1+val2) );
        
}

void solve() 
{
    ll n;cin>>n;
    
    vll a(n);
    
    forl(i,0,n)cin>>a[i];
    
    ll ans = n+(n-1);
    
    forl(i,0,n-2)
    {
        if(chk(i,i+1,i+2,a)==false)
            ans++;
    }
    
    forl(i,0,n-3)
    {
        bool chk1 = false;
        chk1 |= chk(i,i+1,i+2,a);
        chk1 |= chk(i+1,i+2,i+3,a);
        chk1 |= chk(i,i+2,i+3,a);
        chk1 |= chk(i,i+1,i+3,a);
        if(chk1==false)
            ans++;
    }
    cout<<ans<<'\n';
    
} 


int main() {
    
    //fastio
    ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
    
	ll t=1;
	cin>>t;
	
	while(t--)
	{
	    solve();
	}//while(t--)...ends

	return 0;
}

```