#include<iostream>
#include<stdio.h>
#include<cmath>
#include<cstring>
#include<set>
#include<vector>
#include<map>
#include<unordered_map>
#include<algorithm>
#include<sstream>
#include<climits>
#include<utility>
#define fast ios::sync_with_stdio(false);cin.tie(0);
#define MX 1000000000
#define MOD 1000000007
#define fs first
#define sec second
#define vint vector<int>
#define vlong vector<ll>
#define pint pair<int,int>
#define vpint vector<pint >
#define vplong vector<pair<ll,ll> >
#define TEST_CASE int T,number = 0;cin>>T;while(T--){number++;solve(number);}
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loop1(i,a) for(int i=1;i<=a;i++)
#define pb(a) push_back(a)
#define ins insert
#define all(a) (a).begin(), (a).end()
#define mp(x, y) make_pair((x), (y))
#define iter(c) typeof(c.begin())
#define foreach(it, c) for(iter(c) it = c.begin(); it != c.end(); it++)
#define ivec(a,n) vint a(n);loop(i,0,n) cin>>a[i];
#define iarr(a,n) int a[n];loop(i,0,n) cin>>a[i];
#define iset(s,n) set<int> s;loop(i,0,n){int x;cin>>x;s.ins(x);}
#define illvec(a,n) vlong a(n);loop(i,0,n) cin>>a[i];
#define illarr(a,n) ll a[n];loop(i,0,n) cin>>a[i];
#define illset(a,n) set<ll> a;loop(i,0,n) {int x;cin>>x;s.in(x);}
 
typedef long long ll;
 
using namespace std;
 
ll binpow(ll a,ll b)
{
    ll exp = 1000000007;
    a%=exp;
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = ((res) * (a))%exp;
        a = ((a) * (a))%exp;
        b >>= 1;
    }
    return res;
}
 
bool isprime(ll x) {
    for (ll d = 2; d * d <= x; d++) {
        if (x % d == 0)
            return false;
    }
    return true;
}
 
unsigned int countsb(unsigned int n)
{
    unsigned int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

int LCSubStr(string X, string Y, int m, int n)
{
    int LCSufs[m + 1][n + 1];
    int result = 0; 
    for (int i = 0; i <= m; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (i == 0 || j == 0)
                LCSufs[i][j] = 0;
 
            else if (X[i - 1] == Y[j - 1]) {
                LCSufs[i][j] = LCSufs[i - 1][j - 1] + 1;
                result = max(result, LCSufs[i][j]);
            }
            else
                LCSufs[i][j] = 0;
        }
    }
    return result;
}

void solve(int cas)
{
    //cout<<"Case #"<<cas<<": ";
    int n;
    cin>>n;
    ivec(a,n);
    int ans = 0;
    loop(i,0,n)
    {
        loop(j,i,n)
        {
            if(i+2 <= j)
            {
                bool val = 1;
                loop(i1,i,j)
                {
                    loop(i2,i1+1,j)
                    {
                        if((a[i1]>=a[i2] && a[i2]>=a[j]) || (a[i1]<=a[i2] && a[i2]<=a[j])) val = 0;
                    }
                }
                if(!val) break;
            }
            ans++;
        }
    }
    cout<<ans<<"\n";
}

int main()
{
    fast
    TEST_CASE
    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<iostream>
#include<stdio.h>
#include<cmath>
#include<cstring>
#include<set>
#include<vector>
#include<map>
#include<unordered_map>
#include<algorithm>
#include<sstream>
#include<climits>
#include<utility>
#define fast ios::sync_with_stdio(false);cin.tie(0);
#define MX 1000000000
#define MOD 1000000007
#define fs first
#define sec second
#define vint vector<int>
#define vlong vector<ll>
#define pint pair<int,int>
#define vpint vector<pint >
#define vplong vector<pair<ll,ll> >
#define TEST_CASE int T,number = 0;cin>>T;while(T--){number++;solve(number);}
#define loop(i,a,b) for(int i=a;i<b;i++)
#define loop1(i,a) for(int i=1;i<=a;i++)
#define pb(a) push_back(a)
#define ins insert
#define all(a) (a).begin(), (a).end()
#define mp(x, y) make_pair((x), (y))
#define iter(c) typeof(c.begin())
#define foreach(it, c) for(iter(c) it = c.begin(); it != c.end(); it++)
#define ivec(a,n) vint a(n);loop(i,0,n) cin>>a[i];
#define iarr(a,n) int a[n];loop(i,0,n) cin>>a[i];
#define iset(s,n) set<int> s;loop(i,0,n){int x;cin>>x;s.ins(x);}
#define illvec(a,n) vlong a(n);loop(i,0,n) cin>>a[i];
#define illarr(a,n) ll a[n];loop(i,0,n) cin>>a[i];
#define illset(a,n) set<ll> a;loop(i,0,n) {int x;cin>>x;s.in(x);}
 
typedef long long ll;
 
using namespace std;
 
ll binpow(ll a,ll b)
{
    ll exp = 1000000007;
    a%=exp;
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = ((res) * (a))%exp;
        a = ((a) * (a))%exp;
        b >>= 1;
    }
    return res;
}
 
bool isprime(ll x) {
    for (ll d = 2; d * d <= x; d++) {
        if (x % d == 0)
            return false;
    }
    return true;
}
 
unsigned int countsb(unsigned int n)
{
    unsigned int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

int LCSubStr(string X, string Y, int m, int n)
{
    int LCSufs[m + 1][n + 1];
    int result = 0; 
    for (int i = 0; i <= m; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (i == 0 || j == 0)
                LCSufs[i][j] = 0;
 
            else if (X[i - 1] == Y[j - 1]) {
                LCSufs[i][j] = LCSufs[i - 1][j - 1] + 1;
                result = max(result, LCSufs[i][j]);
            }
            else
                LCSufs[i][j] = 0;
        }
    }
    return result;
}

void solve(int cas)
{
    //cout<<"Case #"<<cas<<": ";
    int n;
    cin>>n;
    ivec(a,n);
    int ans = 0;
    loop(i,0,n)
    {
        loop(j,i,n)
        {
            if(i+2 <= j)
            {
                bool val = 1;
                loop(i1,i,j)
                {
                    loop(i2,i1+1,j)
                    {
                        if((a[i1]>=a[i2] && a[i2]>=a[j]) || (a[i1]<=a[i2] && a[i2]<=a[j])) val = 0;
                    }
                }
                if(!val) break;
            }
            ans++;
        }
    }
    cout<<ans<<"\n";
}

int main()
{
    fast
    TEST_CASE
    return 0;
}
```