#include <bits/stdc++.h>
using namespace std;

#define ll              long long
#define nl              <<endl
#define _               << " "
#define pii             pair<int, int>
#define pll             pair<ll, ll>
#define MIN             INT_MIN
#define MAX             LLONG_MAX
#define m               %u
#define f               first
#define s               second

#define res(x)          resize(x)
#define sz()            size()
#define er              erase
#define pb              push_back
#define eleV            vector <ele>
#define all(vec)        vec.begin(), vec.end()
#define rs(A,x)         memset(A, x, sizeof(A))
#define Unique(C)       C.erase(unique(C.begin(), C.end()), C.end())
#define pq(x)           priority_queue<x>
#define neg_pq(x)       priority_queue<x, vector<x>, greater<x>>
#define vec2(C,x,y,tp)  vector<vector<tp> > C(x, vector<tp> (y, 0))

#define FOR(i, m, n)    for(int i = m; i < n; ++i)
#define FORx(i,m,n,x)   for(int i = m; i < n; i += x)
#define FORD(i, m, n)   for(int i = m; i >= n; --i)
#define get(C,a)        FOR(i, 0, a) cin >> C[i]
#define print(C,a)      FOR(i, 0, a) cout << C[i]
#define faster()        cin.tie(0); ios_base::sync_with_stdio(false); cout.tie(0);
#define run()           int t; cin >> t; while (t--)

// #define get2(C,a,b) for(int i=0; i<a; i++) for (int j=0; j<b; j++) cin>>C[i][j]
#define getVector(C) for(int i=0; i<C.size(); i++) cin>>C[i]
// #define getVector2(C) for(int i=0; i<C.size(); i++) for (int j=0; j<C[i].size(); j++) cin>>C[i][j]
// --------------------------------------------------------- //



void reset();
void getip();


void solve()
{
	ll total, a;
	cin >> a;
	vector<ll> C(a);
	getVector(C);

	total = a * 2 - 1;
	if (C.size() > 3) 
        FOR(i, 0, C.sz() - 3)
        {
            if (C[i] > C[i + 1] && C[i + 1] < C[i + 2] && C[i + 2] > C[i + 3] && C[i + 2] > C[i] && C[i + 1] < C[i + 3]) 
                total++;
            else if (C[i] < C[i + 1] && C[i + 1] > C[i + 2] && C[i + 2] < C[i + 3] && C[i + 1] > C[i + 3] && C[i + 2] < C[i]) 
                total++;
        }

	if (C.size() > 2) 
        FOR(i, 0, C.size() - 2)
        {
            if (C[i] > C[i + 1] && C[i + 1] < C[i + 2]) 
                total++;
            else if (C[i] < C[i + 1] && C[i + 1] > C[i + 2]) 
                total++;
        }
	cout << total nl;
}

int main ()
{
    faster();
    run()
    {  
        reset();
        getip();
        solve();
    }
    return 0;
}


// --------------------------------------------------------- //
void getip()
{
    
}

void reset()
{
    
}
### Prompt

Create a solution in Cpp for 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 ll              long long
#define nl              <<endl
#define _               << " "
#define pii             pair<int, int>
#define pll             pair<ll, ll>
#define MIN             INT_MIN
#define MAX             LLONG_MAX
#define m               %u
#define f               first
#define s               second

#define res(x)          resize(x)
#define sz()            size()
#define er              erase
#define pb              push_back
#define eleV            vector <ele>
#define all(vec)        vec.begin(), vec.end()
#define rs(A,x)         memset(A, x, sizeof(A))
#define Unique(C)       C.erase(unique(C.begin(), C.end()), C.end())
#define pq(x)           priority_queue<x>
#define neg_pq(x)       priority_queue<x, vector<x>, greater<x>>
#define vec2(C,x,y,tp)  vector<vector<tp> > C(x, vector<tp> (y, 0))

#define FOR(i, m, n)    for(int i = m; i < n; ++i)
#define FORx(i,m,n,x)   for(int i = m; i < n; i += x)
#define FORD(i, m, n)   for(int i = m; i >= n; --i)
#define get(C,a)        FOR(i, 0, a) cin >> C[i]
#define print(C,a)      FOR(i, 0, a) cout << C[i]
#define faster()        cin.tie(0); ios_base::sync_with_stdio(false); cout.tie(0);
#define run()           int t; cin >> t; while (t--)

// #define get2(C,a,b) for(int i=0; i<a; i++) for (int j=0; j<b; j++) cin>>C[i][j]
#define getVector(C) for(int i=0; i<C.size(); i++) cin>>C[i]
// #define getVector2(C) for(int i=0; i<C.size(); i++) for (int j=0; j<C[i].size(); j++) cin>>C[i][j]
// --------------------------------------------------------- //



void reset();
void getip();


void solve()
{
	ll total, a;
	cin >> a;
	vector<ll> C(a);
	getVector(C);

	total = a * 2 - 1;
	if (C.size() > 3) 
        FOR(i, 0, C.sz() - 3)
        {
            if (C[i] > C[i + 1] && C[i + 1] < C[i + 2] && C[i + 2] > C[i + 3] && C[i + 2] > C[i] && C[i + 1] < C[i + 3]) 
                total++;
            else if (C[i] < C[i + 1] && C[i + 1] > C[i + 2] && C[i + 2] < C[i + 3] && C[i + 1] > C[i + 3] && C[i + 2] < C[i]) 
                total++;
        }

	if (C.size() > 2) 
        FOR(i, 0, C.size() - 2)
        {
            if (C[i] > C[i + 1] && C[i + 1] < C[i + 2]) 
                total++;
            else if (C[i] < C[i + 1] && C[i + 1] > C[i + 2]) 
                total++;
        }
	cout << total nl;
}

int main ()
{
    faster();
    run()
    {  
        reset();
        getip();
        solve();
    }
    return 0;
}


// --------------------------------------------------------- //
void getip()
{
    
}

void reset()
{
    
}
```