#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second 
#define N1 100005
#define N2 200005
#define endl "\n"
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define vll vector<ll>
#define pb push_back
#define for0(i,n) for(ll i=0;i<n;i++)
#define for1(i,n) for(ll i=1;i<=n;i++)
#define cy cout<<"YES\n"
#define cn cout<<"NO\n"
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)

void __print(int x) {cout << x;}
void __print(long x) {cout << x;}
void __print(long long x) {cout << x;}
void __print(unsigned x) {cout << x;}
void __print(unsigned long x) {cout << x;}
void __print(unsigned long long x) {cout << x;}
void __print(float x) {cout << x;}
void __print(double x) {cout << x;}
void __print(long double x) {cout << x;}
void __print(char x) {cout << '\'' << x << '\'';}
void __print(const char *x) {cout << '\"' << x << '\"';}
void __print(const string &x) {cout << '\"' << x << '\"';}
void __print(bool x) {cout << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
void _print() {cout << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif


int check(vector<ll> &ar){
    ll n=ar.size();
    ll ma=1;
    vector<ll> dp(n);
    dp[0]=1;
    for(ll i=1;i<n;i++){
        dp[i]=1;
        for(ll j=0;j<i;j++){
            if(ar[i]>=ar[j]) dp[i]=max(dp[i],1+dp[j]);
        }
        ma=max(ma,dp[i]);
    }
    dp.clear();
    dp.assign(n,1);
    for(ll i=1;i<n;i++){
        dp[i]=1;
        for(ll j=0;j<i;j++){
            if(ar[i]<=ar[j]) dp[i]=max(dp[i],1+dp[j]);
        }
        ma=max(ma,dp[i]);
    }
    return ma>=3;
}




int main()
{
    fastio;
    #ifndef ONLINE_JUDGE
    freopen("./input.txt", "r", stdin);
    freopen("./output.txt", "w", stdout);
    #endif

    ll t=1;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        vector<ll> ar(n);
        for0(i,n){
            cin>>ar[i];
        }
        int cnt=n+n-1;

        for(int i=0;i<n;i++){
            for(int j=i+2;j<n&&j<i+7;j++){
                vector<ll> temp(ar.begin()+i,ar.begin()+j+1);
                if(check(temp)==0) cnt++;
            }
        }

        cout<<cnt<<"\n";

    }
    return 0;
}

### Prompt

Create a solution in cpp for 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;
#define ll long long
#define F first
#define S second 
#define N1 100005
#define N2 200005
#define endl "\n"
#define mod 1000000007
#define all(v) v.begin(),v.end()
#define vll vector<ll>
#define pb push_back
#define for0(i,n) for(ll i=0;i<n;i++)
#define for1(i,n) for(ll i=1;i<=n;i++)
#define cy cout<<"YES\n"
#define cn cout<<"NO\n"
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)

void __print(int x) {cout << x;}
void __print(long x) {cout << x;}
void __print(long long x) {cout << x;}
void __print(unsigned x) {cout << x;}
void __print(unsigned long x) {cout << x;}
void __print(unsigned long long x) {cout << x;}
void __print(float x) {cout << x;}
void __print(double x) {cout << x;}
void __print(long double x) {cout << x;}
void __print(char x) {cout << '\'' << x << '\'';}
void __print(const char *x) {cout << '\"' << x << '\"';}
void __print(const string &x) {cout << '\"' << x << '\"';}
void __print(bool x) {cout << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
void _print() {cout << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif


int check(vector<ll> &ar){
    ll n=ar.size();
    ll ma=1;
    vector<ll> dp(n);
    dp[0]=1;
    for(ll i=1;i<n;i++){
        dp[i]=1;
        for(ll j=0;j<i;j++){
            if(ar[i]>=ar[j]) dp[i]=max(dp[i],1+dp[j]);
        }
        ma=max(ma,dp[i]);
    }
    dp.clear();
    dp.assign(n,1);
    for(ll i=1;i<n;i++){
        dp[i]=1;
        for(ll j=0;j<i;j++){
            if(ar[i]<=ar[j]) dp[i]=max(dp[i],1+dp[j]);
        }
        ma=max(ma,dp[i]);
    }
    return ma>=3;
}




int main()
{
    fastio;
    #ifndef ONLINE_JUDGE
    freopen("./input.txt", "r", stdin);
    freopen("./output.txt", "w", stdout);
    #endif

    ll t=1;
    cin>>t;
    while(t--)
    {
        ll n;
        cin>>n;
        vector<ll> ar(n);
        for0(i,n){
            cin>>ar[i];
        }
        int cnt=n+n-1;

        for(int i=0;i<n;i++){
            for(int j=i+2;j<n&&j<i+7;j++){
                vector<ll> temp(ar.begin()+i,ar.begin()+j+1);
                if(check(temp)==0) cnt++;
            }
        }

        cout<<cnt<<"\n";

    }
    return 0;
}

```