#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;

inline void read(int &x) {
    int s=0;x=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=2e5+5;

int a[N];

int main(){
	int T; cin>>T;
	while(T--){
		int n; cin>>n;
		rep(i,1,n) read(a[i]);
		
		ll res=0;
		rep(i,1,n){
			rep(j,i,min(i+3, n)){
				if(j<=i+1){
					res++;
					continue;
				}
				
				if(j==i+2){
					if(a[i+2]>=a[i+1] && a[i+1]>=a[i] || a[i+2]<=a[i+1] && a[i+1]<=a[i]) break;
					res++;
					// if(a[i+2]>a[i+1] && a[i+1]<a[i] && a[i+2]<=a[1])
				}
				
				if(j==i+3){
					if(a[i+2]>a[i+1] && a[i+1]<a[i]){
						if((a[i+3]>=a[i+2] || a[i+3]<=a[i+1])) break;
						if(a[i+2]>a[i])
							res++;
					}
					
					if(a[i+2]<a[i+1] && a[i+1]>a[i]){
						if((a[i+3]<=a[i+2] || a[i+3]>=a[i+1])) break;
						if(a[i+2]<a[i])
							res++;
					}
				}
				
			}
		}
		
		cout<<res<<endl;
	}
    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
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << endl
#define pb(a) push_back(a)
#define set0(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define ceil(a,b) (a+(b-1))/b
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define ll_INF 0x7f7f7f7f7f7f7f7f
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;

inline void read(int &x) {
    int s=0;x=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=2e5+5;

int a[N];

int main(){
	int T; cin>>T;
	while(T--){
		int n; cin>>n;
		rep(i,1,n) read(a[i]);
		
		ll res=0;
		rep(i,1,n){
			rep(j,i,min(i+3, n)){
				if(j<=i+1){
					res++;
					continue;
				}
				
				if(j==i+2){
					if(a[i+2]>=a[i+1] && a[i+1]>=a[i] || a[i+2]<=a[i+1] && a[i+1]<=a[i]) break;
					res++;
					// if(a[i+2]>a[i+1] && a[i+1]<a[i] && a[i+2]<=a[1])
				}
				
				if(j==i+3){
					if(a[i+2]>a[i+1] && a[i+1]<a[i]){
						if((a[i+3]>=a[i+2] || a[i+3]<=a[i+1])) break;
						if(a[i+2]>a[i])
							res++;
					}
					
					if(a[i+2]<a[i+1] && a[i+1]>a[i]){
						if((a[i+3]<=a[i+2] || a[i+3]>=a[i+1])) break;
						if(a[i+2]<a[i])
							res++;
					}
				}
				
			}
		}
		
		cout<<res<<endl;
	}
    return 0;
}
```