#include <bits/stdc++.h>
using namespace std;
#define ll long long //__int64 __int128
#define ull unsigned long long
#define pb push_back
#define eb emplace_back
#define mst(a, b) memset(a, b, sizeof(a))
#define mCase int T_Case; cin>>T_Case; for(int Case=1;Case<=T_Case;++Case)
#define qm(a, b) (a-a/b*b)
#define mCase int T; scanf("%d", &T); for(int Case=1;Case<=T;++Case)
//srand(time(NULL)); srand(rand()); srand(rand());

const double PI=acos(-1.0);

/*
int P_num[700005], P_cnt; //664579 in 1e7, 5761455 in 1e8
bool isP[10000007];

void GetPrime(int Pn){
	memset(isP, 1, sizeof(isP)), isP[1]=P_cnt=0;
	for(int i=2;i<=Pn;++i){
		if(isP[i]) P_num[++P_cnt]=i;
		for(int j=1;j<=P_cnt && i*P_num[j]<=Pn;++j){
			isP[i*P_num[j]]=0;
			if(!qm(i, P_num[j])) break;
		}
	}
}
*/

//gcd(a,b)*lcm(a,b)=a*b
ll GCD(ll a, ll b, ll t=1){ while(b){ t=b;b=a-a/b*b; a=t;} return a;}
ll LCM(ll a, ll b){ return a/GCD(a, b)*b;}

ll qmul(ll a, ll b, ll p=1000000007){ ll r=0; while(b){ if(b&1) r=(r+a)%p; b>>=1; a=(a+a)%p;} return r;}
ll Kpow(ll x, ll n, ll p=1000000007){ ll r=1; for(;n;n>>=1, x=qm(x*x, p)) if(n&1) r=qm(r*x, p); return r;}

const double eps=1e-6;
#define P pair<ll, ll>
const long long LINF=0x3f3f3f3f3f3f3f3f; //0x7f7f7f7f7f7f7f7f

const int mod=1000000007; // 998244353
const int INF=0x3f3f3f3f; //0x7f7f7f7f
const int maxn=(int)2e5+5;

int n;
ll s[maxn];

void work(){
    cin>>n;
    for(int i=1;i<=n;++i) cin>>s[i];
    ll ans=2*n-1;
    for(int i=1;i<=n-2;++i){
        if(s[i]>=s[i+1] and s[i+1]>=s[i+2] or s[i]<=s[i+1] and s[i+1]<=s[i+2]) continue;
        ++ans;
    }
    for(int i=1;i<=n-3;++i){
        if((s[i+1]<s[i] and s[i]<s[i+2] or s[i+2]<s[i] and s[i]<s[i+1]) and min(s[i+1], s[i+2])<s[i+3] and s[i+3]<max(s[i+1], s[i+2])) ++ans;
    }
    cout<<ans<<endl;
}

int main(){
	mCase{ work();}
	//work();

	return 0;
}

### Prompt

Please provide a Cpp coded solution 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 <bits/stdc++.h>
using namespace std;
#define ll long long //__int64 __int128
#define ull unsigned long long
#define pb push_back
#define eb emplace_back
#define mst(a, b) memset(a, b, sizeof(a))
#define mCase int T_Case; cin>>T_Case; for(int Case=1;Case<=T_Case;++Case)
#define qm(a, b) (a-a/b*b)
#define mCase int T; scanf("%d", &T); for(int Case=1;Case<=T;++Case)
//srand(time(NULL)); srand(rand()); srand(rand());

const double PI=acos(-1.0);

/*
int P_num[700005], P_cnt; //664579 in 1e7, 5761455 in 1e8
bool isP[10000007];

void GetPrime(int Pn){
	memset(isP, 1, sizeof(isP)), isP[1]=P_cnt=0;
	for(int i=2;i<=Pn;++i){
		if(isP[i]) P_num[++P_cnt]=i;
		for(int j=1;j<=P_cnt && i*P_num[j]<=Pn;++j){
			isP[i*P_num[j]]=0;
			if(!qm(i, P_num[j])) break;
		}
	}
}
*/

//gcd(a,b)*lcm(a,b)=a*b
ll GCD(ll a, ll b, ll t=1){ while(b){ t=b;b=a-a/b*b; a=t;} return a;}
ll LCM(ll a, ll b){ return a/GCD(a, b)*b;}

ll qmul(ll a, ll b, ll p=1000000007){ ll r=0; while(b){ if(b&1) r=(r+a)%p; b>>=1; a=(a+a)%p;} return r;}
ll Kpow(ll x, ll n, ll p=1000000007){ ll r=1; for(;n;n>>=1, x=qm(x*x, p)) if(n&1) r=qm(r*x, p); return r;}

const double eps=1e-6;
#define P pair<ll, ll>
const long long LINF=0x3f3f3f3f3f3f3f3f; //0x7f7f7f7f7f7f7f7f

const int mod=1000000007; // 998244353
const int INF=0x3f3f3f3f; //0x7f7f7f7f
const int maxn=(int)2e5+5;

int n;
ll s[maxn];

void work(){
    cin>>n;
    for(int i=1;i<=n;++i) cin>>s[i];
    ll ans=2*n-1;
    for(int i=1;i<=n-2;++i){
        if(s[i]>=s[i+1] and s[i+1]>=s[i+2] or s[i]<=s[i+1] and s[i+1]<=s[i+2]) continue;
        ++ans;
    }
    for(int i=1;i<=n-3;++i){
        if((s[i+1]<s[i] and s[i]<s[i+2] or s[i+2]<s[i] and s[i]<s[i+1]) and min(s[i+1], s[i+2])<s[i+3] and s[i+3]<max(s[i+1], s[i+2])) ++ans;
    }
    cout<<ans<<endl;
}

int main(){
	mCase{ work();}
	//work();

	return 0;
}

```