#include<algorithm>
#include<iostream>
#include<sstream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<set>
#define AC 0
#define endl '\n'
#define PI acos(-1)
#define Please return
#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int lcm(int a,int b){return a*b/gcd(a,b);}
int factorials(int a){if(a==0)return 1;return a*factorials(a-1);}
void fastio(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);}
int qpow(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a;b>>=1;a=a*a;}return ans;}
int qpow(int a,int b,int m){int ans=1%m;while(b){if(b&1)ans=ans*a%m;b>>=1;a=a*a%m;}return ans;}
int exgcd(int a,int b,int&x,int&y){if(!b){x=1,y=0;return a;}int r=exgcd(b,a%b,x,y);int te=y;y=x-(a/b)*y;x=te;return r;}

int a[N];

int check(int a,int b,int c)
{
    return !(a>=b&&b>=c||a<=b&&b<=c);
}

void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    int ans=2*n-1;
    for(int i=3;i<=n;++i)
    {
        ans+=check(a[i],a[i-1],a[i-2]);
    }
    for(int i=4;i<=n;++i)
    {
        ans+=check(a[i],a[i-1],a[i-2])&&check(a[i],a[i-1],a[i-3])&&check(a[i],a[i-2],a[i-3])&&check(a[i-1],a[i-2],a[i-3]);
    }
    cout<<ans<<endl;
}

signed main()
{
    fastio();
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
    Please AC;
}
### Prompt

Develop a solution in cpp 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<algorithm>
#include<iostream>
#include<sstream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<set>
#define AC 0
#define endl '\n'
#define PI acos(-1)
#define Please return
#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int lcm(int a,int b){return a*b/gcd(a,b);}
int factorials(int a){if(a==0)return 1;return a*factorials(a-1);}
void fastio(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);}
int qpow(int a,int b){int ans=1;while(b){if(b&1)ans=ans*a;b>>=1;a=a*a;}return ans;}
int qpow(int a,int b,int m){int ans=1%m;while(b){if(b&1)ans=ans*a%m;b>>=1;a=a*a%m;}return ans;}
int exgcd(int a,int b,int&x,int&y){if(!b){x=1,y=0;return a;}int r=exgcd(b,a%b,x,y);int te=y;y=x-(a/b)*y;x=te;return r;}

int a[N];

int check(int a,int b,int c)
{
    return !(a>=b&&b>=c||a<=b&&b<=c);
}

void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    int ans=2*n-1;
    for(int i=3;i<=n;++i)
    {
        ans+=check(a[i],a[i-1],a[i-2]);
    }
    for(int i=4;i<=n;++i)
    {
        ans+=check(a[i],a[i-1],a[i-2])&&check(a[i],a[i-1],a[i-3])&&check(a[i],a[i-2],a[i-3])&&check(a[i-1],a[i-2],a[i-3]);
    }
    cout<<ans<<endl;
}

signed main()
{
    fastio();
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int t;
    t=1;
    cin>>t;
    while(t--)
    {
        solve();
    }
    Please AC;
}
```