#include<bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define precise(num,by) cout<<fixed<<setprecision(by)<<num<<" ";
#define int long long
#define mod 1000000007
#define mod2 998244353
#define fir first
#define sec second
#define all(v) v.begin(),v.end()
#define vil vector<long long int>
#define vi vector<int>
#define vi2 vector<vector<int>>
#define vb vector<bool>
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define ub(x) upper_bound(x)
#define lb(x) lower_bound(x)
#define pil pair<long,long>
#define minheap priority_queue<int,vector<int>,greater<int>>// min at top
#define minheap2 priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>// min at top
#define print(x) cout<<((x==1)?"YES":"NO")<<endl;
#define vin(n,arr) for(int i=0;i<n;i++)cin>>arr[i];
#define vinmp(n,arr,mp) for(int i=0;i<n;i++){int temp;cin>>temp;arr[i]=temp;mp[temp]++;}
#define input1 int n;cin>>n;vi arr(n);vin(n,arr);
#define input2 int n;cin>>n;vi arr(n);unordered_map<int,int>mp;vinmp(n,arr,mp);
#define input3 int n,k;cin>>n>>k;vi arr(n);vin(n,arr);
#define rep(i,a,b)        for(int i=a;i<b;i++)
const int maxn = 1e5 + 5;
const int N = 1e6 + 5;
int dirx[4] = {0, 0, -1, 1};
int diry[4] = { -1, 1, 0, 0};
char dir[4] = {'R', 'L', 'D', 'U'};//modify as per need;
int a[(int)2e5+5];
bool check(vector<int> &v){
	int n = v.size();
	rep(i,0,n){
		rep(j,i+1,n){
			rep(k,j+1,n){
				if((v[i] >= v[j] && v[j] >= v[k]) ||
					(v[i] <= v[j] && v[j] <= v[k])){
					return true;
				}
			}
		}
	}
	return false;
}

void solve() {
	int n;
	cin >> n;
	rep(i,0,n){
		cin >> a[i];
	}
	
	int ans = 0;
	rep(i,0,n){
		vector<int> v;
		rep(j,i,n){
			v.pb(a[j]);
			if(check(v)) break;
			ans++;
		}
	}
	cout << ans << "\n";
}
signed  main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	FAST;
	int t;
	// t = 1;
	cin >> t;
	while (t--)
		solve();
	return 0;
}	
### Prompt

Please create a solution in Cpp 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 FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define precise(num,by) cout<<fixed<<setprecision(by)<<num<<" ";
#define int long long
#define mod 1000000007
#define mod2 998244353
#define fir first
#define sec second
#define all(v) v.begin(),v.end()
#define vil vector<long long int>
#define vi vector<int>
#define vi2 vector<vector<int>>
#define vb vector<bool>
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define ub(x) upper_bound(x)
#define lb(x) lower_bound(x)
#define pil pair<long,long>
#define minheap priority_queue<int,vector<int>,greater<int>>// min at top
#define minheap2 priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>// min at top
#define print(x) cout<<((x==1)?"YES":"NO")<<endl;
#define vin(n,arr) for(int i=0;i<n;i++)cin>>arr[i];
#define vinmp(n,arr,mp) for(int i=0;i<n;i++){int temp;cin>>temp;arr[i]=temp;mp[temp]++;}
#define input1 int n;cin>>n;vi arr(n);vin(n,arr);
#define input2 int n;cin>>n;vi arr(n);unordered_map<int,int>mp;vinmp(n,arr,mp);
#define input3 int n,k;cin>>n>>k;vi arr(n);vin(n,arr);
#define rep(i,a,b)        for(int i=a;i<b;i++)
const int maxn = 1e5 + 5;
const int N = 1e6 + 5;
int dirx[4] = {0, 0, -1, 1};
int diry[4] = { -1, 1, 0, 0};
char dir[4] = {'R', 'L', 'D', 'U'};//modify as per need;
int a[(int)2e5+5];
bool check(vector<int> &v){
	int n = v.size();
	rep(i,0,n){
		rep(j,i+1,n){
			rep(k,j+1,n){
				if((v[i] >= v[j] && v[j] >= v[k]) ||
					(v[i] <= v[j] && v[j] <= v[k])){
					return true;
				}
			}
		}
	}
	return false;
}

void solve() {
	int n;
	cin >> n;
	rep(i,0,n){
		cin >> a[i];
	}
	
	int ans = 0;
	rep(i,0,n){
		vector<int> v;
		rep(j,i,n){
			v.pb(a[j]);
			if(check(v)) break;
			ans++;
		}
	}
	cout << ans << "\n";
}
signed  main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	FAST;
	int t;
	// t = 1;
	cin >> t;
	while (t--)
		solve();
	return 0;
}	
```