#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define ll long long
#define dd double
#define MOD1 1000000007
#define MOD2 998244353
#define nl cout<<endl
#define rt ll Q[100005]={0}
#define mp make_pair
#define test() ll t;cin>>t;while(t--)
#define pb push_back
#define ff first    
#define ss second
#define all(v) v.begin(),v.end()
#define s(ar,n) sort(ar,ar+n)
#define rs(ar,n) sort(ar, ar+n, greater<ll>()) 
#define oa(a,n) for(ll i=0;i<n;i++)cout<<a[i]<<" ";nl
#define cn(a,n) for(ll i=0;i<n;i++)cin>>a[i];
#define ov(a,n) for(ll i=n-1;i>=0;i--)cout<<a[i]<<" ";nl
#define ovp(a,n) for(ll i=0;i<n;i++)cout<<a[i].ff<<" "<<a[i].ss<<endl;
#define maxa(ar,N) *max_element(ar,ar+N)
#define mina(ar,N) *min_element(ar,ar+N)
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
typedef pair<ll,ll> pii;
ll powe(ll n,ll m){if(m==0)return 1;ll t=powe(n,m/2);if(m%2==0)return (t*t);return (((t*t))*n);}
ll mpowe(ll n,ll m,ll MOD){if(m==0)return 1;ll t=mpowe(n,m/2,MOD);t%=MOD;if(m%2==0)return (t*t)%MOD;return (((t*t)%MOD)*n)%MOD;}
ll logtwo(ll n){if(n==1)return 0;if(n==0) return -1;return logtwo(n/2)+1;}
ll check(vector<pair<ll,ll> > &v)
{
    ll flag=1;
    
    for (int i = 0; i < v.size(); ++i)
    {
        for (int j = i+1; j < v.size(); ++j)
        {
            for (int k = j+1; k < v.size(); ++k)
            {
                vector<ll> x(3);
                x[0] = abs(v[i].ff-v[j].ff) + abs(v[i].ss-v[j].ss);
                x[1] = abs(v[i].ff-v[k].ff) + abs(v[i].ss-v[k].ss);
                x[2] = abs(v[k].ff-v[j].ff) + abs(v[k].ss-v[j].ss);
                sort(all(x));
                if(x[2]==x[0]+x[1])
                    flag=0;
            }
        }
    }
    //nl;
    //cout<<flag<<endl;
    return  flag;
}

int main()
{
    fastio();
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t=1;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        ll a[n];
        cn(a,n);
        ll ans = 0;
        for (int i = 0; i < n; ++i)
        {
            vector<pair<ll,ll>> v;
            int j=i;
            while(j>=0)
            {
                v.pb({a[j],j});
                if(check(v))
                    ans++;
                else
                    break;
                j--;
            }
        }
        cout<<ans<<endl;
    }
    
}
### Prompt

Your challenge is to write 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 <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define ll long long
#define dd double
#define MOD1 1000000007
#define MOD2 998244353
#define nl cout<<endl
#define rt ll Q[100005]={0}
#define mp make_pair
#define test() ll t;cin>>t;while(t--)
#define pb push_back
#define ff first    
#define ss second
#define all(v) v.begin(),v.end()
#define s(ar,n) sort(ar,ar+n)
#define rs(ar,n) sort(ar, ar+n, greater<ll>()) 
#define oa(a,n) for(ll i=0;i<n;i++)cout<<a[i]<<" ";nl
#define cn(a,n) for(ll i=0;i<n;i++)cin>>a[i];
#define ov(a,n) for(ll i=n-1;i>=0;i--)cout<<a[i]<<" ";nl
#define ovp(a,n) for(ll i=0;i<n;i++)cout<<a[i].ff<<" "<<a[i].ss<<endl;
#define maxa(ar,N) *max_element(ar,ar+N)
#define mina(ar,N) *min_element(ar,ar+N)
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
typedef pair<ll,ll> pii;
ll powe(ll n,ll m){if(m==0)return 1;ll t=powe(n,m/2);if(m%2==0)return (t*t);return (((t*t))*n);}
ll mpowe(ll n,ll m,ll MOD){if(m==0)return 1;ll t=mpowe(n,m/2,MOD);t%=MOD;if(m%2==0)return (t*t)%MOD;return (((t*t)%MOD)*n)%MOD;}
ll logtwo(ll n){if(n==1)return 0;if(n==0) return -1;return logtwo(n/2)+1;}
ll check(vector<pair<ll,ll> > &v)
{
    ll flag=1;
    
    for (int i = 0; i < v.size(); ++i)
    {
        for (int j = i+1; j < v.size(); ++j)
        {
            for (int k = j+1; k < v.size(); ++k)
            {
                vector<ll> x(3);
                x[0] = abs(v[i].ff-v[j].ff) + abs(v[i].ss-v[j].ss);
                x[1] = abs(v[i].ff-v[k].ff) + abs(v[i].ss-v[k].ss);
                x[2] = abs(v[k].ff-v[j].ff) + abs(v[k].ss-v[j].ss);
                sort(all(x));
                if(x[2]==x[0]+x[1])
                    flag=0;
            }
        }
    }
    //nl;
    //cout<<flag<<endl;
    return  flag;
}

int main()
{
    fastio();
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t=1;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        ll a[n];
        cn(a,n);
        ll ans = 0;
        for (int i = 0; i < n; ++i)
        {
            vector<pair<ll,ll>> v;
            int j=i;
            while(j>=0)
            {
                v.pb({a[j],j});
                if(check(v))
                    ans++;
                else
                    break;
                j--;
            }
        }
        cout<<ans<<endl;
    }
    
}
```