#include <bits/stdc++.h>
#include <iostream>
using namespace std;
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define fo(i,n) for(ll i=0;i<n;i++)
#define fo1(i,n) for(ll i=1;i<=n;i++)
#define loop(i,a,b)for(ll i=a;i<=b;i++)
#define loopr(i,a,b)for(ll i=b;i>=a;i--)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
#define vll vector<ll> 
#define vvl vector<vll>
#define vpll vector<pll>
#define pll pair<ll,ll>
#define F first
#define S second
#define MOD 1000000007
ll max(ll a,ll b){if (a>b) return a; else return b;}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b, a%b);}
ll lcm(ll a, ll b){return a*b/gcd(a, b);}
ll fexp(ll a, ll b){ll ans = 1;while(b){if(b&1) ans = ans*a%MOD; b/=2;a=a*a%MOD;}return ans;}
ll inverse(ll a, ll p){return fexp(a, p-2);}
using namespace std;

//take care of long long

//fast I/O 
auto optimizer = []() {  // makes I/O fast
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  return 0;
}();

//seive
ll N = 1e5;
vll lpf(N+1,0);
void leastPrimeFactor()
{
    lpf[1] = 1;
    for (ll i = 2; i <= N; i++)
    {
        if(lpf[i] == 0)
        {
            lpf[i] = i;
            for (ll j = 2*i; j <= N; j += i)
            	if (lpf[j] == 0)
                	lpf[j] = i;
        } 
    }
}

int main()
{
	ll t=1;
	cin>>t;
	while(t--)
	{
		ll n;
	  	cin>>n;
	  	vector<ll> vc(n);
	  	for(ll i=0;i<n;i++)
	  		cin>>vc[i];
	  	ll ans=n+n-1;
	  	//ll add=0;
  			//bool var=false;
  			for(ll ln=3;ln<=5;ln++)
  			{
  				ll st=0, en=ln-1;
  				while(en<n)
  				{
  					bool flg=true;
  					for(ll p1=st;p1<=en&&flg;p1++)
  					{
  						for(ll p2=p1+1;p2<=en&&flg;p2++)
  						{
  							for(ll p3=p2+1;p3<=en&&flg;p3++)
  							{
  								if( (vc[p1]<=vc[p2]&&vc[p2]<=vc[p3]) || (vc[p1]>=vc[p2]&&vc[p2]>=vc[p3]) )
  								{
  									flg=false;
  									break;
  								}

  							}
  						}
  					}

  					if(flg)
  					{
  						ans++;
  					}
  					st++;
  					en++;
  				}
  			}
	  		//ans+=add;
	  		//cout<<add<<" ";

	  	//cout<<endl;
	  	cout<<ans<<endl;
	}
	return 0;
}
### Prompt

Your task is to create 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>
#include <iostream>
using namespace std;
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define fo(i,n) for(ll i=0;i<n;i++)
#define fo1(i,n) for(ll i=1;i<=n;i++)
#define loop(i,a,b)for(ll i=a;i<=b;i++)
#define loopr(i,a,b)for(ll i=b;i>=a;i--)
#define all(x) x.begin(), x.end()
#define sz(x) (ll)(x).size()
#define vll vector<ll> 
#define vvl vector<vll>
#define vpll vector<pll>
#define pll pair<ll,ll>
#define F first
#define S second
#define MOD 1000000007
ll max(ll a,ll b){if (a>b) return a; else return b;}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b, a%b);}
ll lcm(ll a, ll b){return a*b/gcd(a, b);}
ll fexp(ll a, ll b){ll ans = 1;while(b){if(b&1) ans = ans*a%MOD; b/=2;a=a*a%MOD;}return ans;}
ll inverse(ll a, ll p){return fexp(a, p-2);}
using namespace std;

//take care of long long

//fast I/O 
auto optimizer = []() {  // makes I/O fast
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  return 0;
}();

//seive
ll N = 1e5;
vll lpf(N+1,0);
void leastPrimeFactor()
{
    lpf[1] = 1;
    for (ll i = 2; i <= N; i++)
    {
        if(lpf[i] == 0)
        {
            lpf[i] = i;
            for (ll j = 2*i; j <= N; j += i)
            	if (lpf[j] == 0)
                	lpf[j] = i;
        } 
    }
}

int main()
{
	ll t=1;
	cin>>t;
	while(t--)
	{
		ll n;
	  	cin>>n;
	  	vector<ll> vc(n);
	  	for(ll i=0;i<n;i++)
	  		cin>>vc[i];
	  	ll ans=n+n-1;
	  	//ll add=0;
  			//bool var=false;
  			for(ll ln=3;ln<=5;ln++)
  			{
  				ll st=0, en=ln-1;
  				while(en<n)
  				{
  					bool flg=true;
  					for(ll p1=st;p1<=en&&flg;p1++)
  					{
  						for(ll p2=p1+1;p2<=en&&flg;p2++)
  						{
  							for(ll p3=p2+1;p3<=en&&flg;p3++)
  							{
  								if( (vc[p1]<=vc[p2]&&vc[p2]<=vc[p3]) || (vc[p1]>=vc[p2]&&vc[p2]>=vc[p3]) )
  								{
  									flg=false;
  									break;
  								}

  							}
  						}
  					}

  					if(flg)
  					{
  						ans++;
  					}
  					st++;
  					en++;
  				}
  			}
	  		//ans+=add;
	  		//cout<<add<<" ";

	  	//cout<<endl;
	  	cout<<ans<<endl;
	}
	return 0;
}
```