//#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define inf 0x3f3f3f3f
#define INF 0x7fffffff
#define infll 0x3f3f3f3f3f3f3f3f
#define il inline
#define re register
#define pb push_back
#define db double
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define puu pair<ull,ull>
#define MP make_pair
#define lowbit(x) x&(-x)
#define fi first
#define se second
#define debug(a) cout<<#a<<" "<<a<<'\n';
#define RAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define grand(l,r) uniform_int_distribution<int>(l,r)(rng)
il ll read()
{
	char ch = getchar();
	ll p = 1,data = 0;
	while(ch<'0'||ch>'9')
	{
		if(ch == '-')p = -1;
		ch = getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		data = data*10+(ch^48);
		ch = getchar();
	}
	return p*data;
}
il ll qpow(ll a,ll b)
{
	ll r = 1;
	while(b)
	{
		if(b&1)r = a*r;
		a = a*a;
		b>>=1;
	}
	return r;
}
void exgcd(ll a, ll b, ll &x,ll &y)
{
	if(!b) x = 1, y = 0;
	else
	{
		exgcd(b, a % b, y, x);
		y -= x * (a / b);
	}
}
const int mod = 1e9+7,maxn = 2e5+5;
int a[maxn],vis[maxn];
int main()
{
	int T = read();
	while(T--)
	{
		int n = read();
		for(int i = 1; i <= n; i++)
			a[i] = read(),vis[i] = 0;
		int ans = 2*n-1;
		for(int i = 1; i <= n-2; i++)
			if((a[i+1] > a[i] && a[i+2] < a[i+1]) || (a[i+1] < a[i] && a[i+2] > a[i+1]))
				ans++,vis[i] = (a[i+1]>=a[i]?1:-1);
		for(int i = 1; i <= n-3; i++)
			if(vis[i])
			{
				if(vis[i] == 1 && a[i+3] < a[i+1] && a[i+3] > a[i+2] && a[i+2] < a[i])
					ans++;
				else if(vis[i] == -1 && a[i+3] > a[i+1] && a[i+3] < a[i+2] && a[i+2] > a[i])
					ans++;	
			}		
		printf("%d\n",ans);	
	}
	return 0;
}


### Prompt

Generate 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
//#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define inf 0x3f3f3f3f
#define INF 0x7fffffff
#define infll 0x3f3f3f3f3f3f3f3f
#define il inline
#define re register
#define pb push_back
#define db double
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define puu pair<ull,ull>
#define MP make_pair
#define lowbit(x) x&(-x)
#define fi first
#define se second
#define debug(a) cout<<#a<<" "<<a<<'\n';
#define RAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define grand(l,r) uniform_int_distribution<int>(l,r)(rng)
il ll read()
{
	char ch = getchar();
	ll p = 1,data = 0;
	while(ch<'0'||ch>'9')
	{
		if(ch == '-')p = -1;
		ch = getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		data = data*10+(ch^48);
		ch = getchar();
	}
	return p*data;
}
il ll qpow(ll a,ll b)
{
	ll r = 1;
	while(b)
	{
		if(b&1)r = a*r;
		a = a*a;
		b>>=1;
	}
	return r;
}
void exgcd(ll a, ll b, ll &x,ll &y)
{
	if(!b) x = 1, y = 0;
	else
	{
		exgcd(b, a % b, y, x);
		y -= x * (a / b);
	}
}
const int mod = 1e9+7,maxn = 2e5+5;
int a[maxn],vis[maxn];
int main()
{
	int T = read();
	while(T--)
	{
		int n = read();
		for(int i = 1; i <= n; i++)
			a[i] = read(),vis[i] = 0;
		int ans = 2*n-1;
		for(int i = 1; i <= n-2; i++)
			if((a[i+1] > a[i] && a[i+2] < a[i+1]) || (a[i+1] < a[i] && a[i+2] > a[i+1]))
				ans++,vis[i] = (a[i+1]>=a[i]?1:-1);
		for(int i = 1; i <= n-3; i++)
			if(vis[i])
			{
				if(vis[i] == 1 && a[i+3] < a[i+1] && a[i+3] > a[i+2] && a[i+2] < a[i])
					ans++;
				else if(vis[i] == -1 && a[i+3] > a[i+1] && a[i+3] < a[i+2] && a[i+2] > a[i])
					ans++;	
			}		
		printf("%d\n",ans);	
	}
	return 0;
}


```