#include<bits/stdc++.h>
using namespace std;  
#define int long long
#define double long double
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define M2 1000000009
#define M1 998244353
#define inf 1e18 
bool isprime(int n){
    	if(n==1) return false;
    	for(int i = 2;i*i<=n;i++){
    		if(n%i==0) return false;
		}
		return true;
}
int gcd(int a, int b){ 
    if (b == 0){
    	return a;
	} 
    return gcd(b, a % b);
}
int lcm(int a,int b){
	return (a*b)/gcd(a,b);
}
int power(int x,int y){  
    int res=1;
    if(x==0)return 0;  
    while(y>0){  
        if(y&1){
        	res*=x;
        	//res%=p;
		}   
        y=y>>1;  
        x=(x*x); 
		//x%=p;
		//res%=p; 
    }  
    return res;  
}
int modInverse(int n, int p){
    return power(n, p-2);
}
/*      You are doing good, keep coding.          */
vector<int> a;
bool isgood(int l,int r){
	for(int i=l;i<=r;i++){
		for(int j=i+1;j<=r;j++){
			for(int k=j+1;k<=r;k++){
				if(a[i]>=a[j] && a[j]>=a[k]){
					return false;
				}
				if(a[i]<=a[j] && a[j]<=a[k]){
					return false;
				}
			}
		}
	}
	return true;
}
signed main(){
	FAST
	int i,j,k,zx,t;
	zx=1;
	cin>>zx;
	while(zx--){
		int n;
		a.clear();
		cin>>n;
		for(i=0;i<n;i++){
			int u;
			cin>>u;
			a.push_back(u);
		}
		int ans=0;
		for(i=0;i<n;i++){
			for(j=i;j<n;j++){
				if(j<n){
					if(isgood(i,j)){
						ans+=1;
					}
					else{
						break;
					}	
				}
				else{
					break;
				}
			}
		}
		cout<<ans<<endl;
	}
}

### 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>
using namespace std;  
#define int long long
#define double long double
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define M2 1000000009
#define M1 998244353
#define inf 1e18 
bool isprime(int n){
    	if(n==1) return false;
    	for(int i = 2;i*i<=n;i++){
    		if(n%i==0) return false;
		}
		return true;
}
int gcd(int a, int b){ 
    if (b == 0){
    	return a;
	} 
    return gcd(b, a % b);
}
int lcm(int a,int b){
	return (a*b)/gcd(a,b);
}
int power(int x,int y){  
    int res=1;
    if(x==0)return 0;  
    while(y>0){  
        if(y&1){
        	res*=x;
        	//res%=p;
		}   
        y=y>>1;  
        x=(x*x); 
		//x%=p;
		//res%=p; 
    }  
    return res;  
}
int modInverse(int n, int p){
    return power(n, p-2);
}
/*      You are doing good, keep coding.          */
vector<int> a;
bool isgood(int l,int r){
	for(int i=l;i<=r;i++){
		for(int j=i+1;j<=r;j++){
			for(int k=j+1;k<=r;k++){
				if(a[i]>=a[j] && a[j]>=a[k]){
					return false;
				}
				if(a[i]<=a[j] && a[j]<=a[k]){
					return false;
				}
			}
		}
	}
	return true;
}
signed main(){
	FAST
	int i,j,k,zx,t;
	zx=1;
	cin>>zx;
	while(zx--){
		int n;
		a.clear();
		cin>>n;
		for(i=0;i<n;i++){
			int u;
			cin>>u;
			a.push_back(u);
		}
		int ans=0;
		for(i=0;i<n;i++){
			for(j=i;j<n;j++){
				if(j<n){
					if(isgood(i,j)){
						ans+=1;
					}
					else{
						break;
					}	
				}
				else{
					break;
				}
			}
		}
		cout<<ans<<endl;
	}
}

```